发现了一种$O(n)$的单调栈算法。
记录一个$next$数组，表示右边第一个大于这个位置的数的位置，那么我们分两种情况讨论：

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

#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] << " ";
}