「NOIP初赛 2018」T1

题目大意：给定一个长度为 $n$ 的序列 $a$，对于每个 $a[i]$ 输出后面第一个比它大的数的位置。$n \leq 10^7$

双向链表

$L[i]$ 维护 $i$ 左边的数，$R[i]$ 维护 $i$ 右边的数，从小到大删除每一个数。

这个做法是今天的初赛给出的，缺点是需要离散化，复杂度带 $\log$，如果不离散化就必须满足 $a$ 是一个排列。

单调栈

从右往左扫描整个序列，维护一个单增的单调栈。

#include <cstdio>

const int N = 10000005;
int a[N], n, sta[N][2], top, ans[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = n; i >= 1; --i) {
        while (top && sta[top][1] <= a[i]) --top;
        ans[i] = top ? sta[top][0] : n + 1;
        sta[++top][0] = i, sta[top][1] = a[i];
    }
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    return 0;
}

时间复杂度 $O(n)$