发现了一种O(n)的单调栈算法

发现了一种

O(n)

的单调栈算法。
记录一个

next

数组，表示右边第一个大于这个位置的数的位置，那么我们分两种情况讨论：

1.a_{i+1}>a_i,next_i=i+1\\ 2.a_{i+1}<a_i,则记录变量j=i+1一直跳j=next_{j}直到a_j>a_i,next_i=j

求大佬证实/伪（洛谷题目单调栈模板已通过）

CPP

#include <bits/stdc++.h>
using namespace std;
long long last[3000005] , a[3000005];
int main ()
{
    ios :: sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
	int n;
	cin >> n;
    for (int i = 1;i <= n;i ++) cin >> a[i];
    for (int i = n - 1;i >= 1;i --)
        if (a[i] < a[i + 1]) last[i] = i + 1;
        else
        {
            int j = last[i + 1];
            while (j && a[j] < a[i]) j = last[j];
            last[i] = j;
        }
    for (int i = 1;i <= n;i ++) cout << last[i] << " ";
}

发现了一种O(n)的单调栈算法

讨论操作

回复

相关推荐

发现了一种O(n)的单调栈算法