题目地址：

题目描述： 给出项数为 n n n的整数数列 a 1 … n a_{1 dots n} a1…n。定义函数 f ( i ) f(i) f(i)代表数列中第 i i i个元素之后第一个大于 a i a_i ai的元素的下标，即 f ( i ) = min ⁡ i < j ≤ n , a j > a i { j } f(i)=min_{i<jleq n, a_j > a_i} {j} f(i)=mini<j≤n,aj>ai{ j}。若不存在，则 f ( i ) = 0 f(i)=0 f(i)=0。试求出 f ( 1 … n ) f(1dots n) f(1…n)。

输入格式： 第一行一个正整数 n n n。第二行 n n n个正整数 a 1 … n a_{1dots n} a1…n。

输出格式： 一行 n n n个整数 f ( 1 … n ) f(1dots n) f(1…n)的值。

数据范围： 对于 30 % 30\% 30%的数据， n ≤ 100 n≤100 n≤100； 对于 60 % 60\% 60%的数据， n ≤ 5 × 1 0 3 nleq 5 imes 10^3 n≤5×103； 对于 100 % 100\% 100%的数据， 1 ≤ n ≤ 3 × 1 0 6 1 le nleq 3 imes 10^6 1≤n≤3×106， 1 ≤ a i ≤ 1 0 9 1leq a_ileq 10^9 1≤ai≤109。

开一个严格单调上升栈，如果栈非空且栈顶所指数字小于了新来的数，则找到了其右边第一个比其大的数的下标。代码如下：

#include <iostream>
using namespace std;

const int N = 3e6 + 10;
int n;
int stk[N], top;
int a[N], res[N];

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

    for (int i = 1; i <= n; i++) {
          
   
        while(top && a[stk[top - 1]] < a[i]) {
          
   
            res[stk[top - 1]] = i;
            top--;
        }

        stk[top++] = i;
    }

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

    return 0;
}

时空复杂度 O ( n ) O(n) O(n)。