(单调栈) $O(n^2)$

解析 请转到秦淮岸大佬的分享 2019年4月6日单调栈讲义 分析的非常棒 然后分享一下自己写的代码

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int a[N];
int b[N];

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;

    for (int i = 1; i <= n; ++ i ) cin>>a[i];

    stack<int> stk;

    for (int i = 1; i <= n; ++ i ) 
    {
        if (stk.empty()) stk.push(i);
        else 
        {
            while (!stk.empty() && a[i] > a[stk.top()])
            {
                b[stk.top()] = i;
                stk.pop();
            }

            stk.push(i);
        }
    }

    for (int i = 1; i <= n; ++ i ) cout<<b[i]<<endl;

    return 0;
}