单调栈

题目描述

给出项数为 $n$ 的整数数列 $a_{1\dots n}$。

$1\le n\le 3\times {10}^6$，$1\le a_i\le {10}^9$。

定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标，即 $f(i)=\underset{i<j\le n,a_j>a_i}{min}\{j\}$。若不存在，则 $f(i)=0$。

试求出 $f(1\dots n)$。

Solution

这个基础算法经常困住我，必须解决掉

倒着遍历：

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> stk;
    for (int i = n;i >= 1;i--) {
        while (stk.size() && a[i] >= a[stk.back()]) stk.pop_back();
        if (stk.size())f[i] = stk.back();
        stk.push_back(i);
    }
    for (int i = 1;i <= n;i++)cout << f[i] << " ";
}

正着遍历：

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> stk;
    for (int i = 1;i <= n;i++) {
        while (stk.size() && a[i] > a[stk.back()])f[stk.back()] = i, stk.pop_back();
        stk.push_back(i);
    }
    for (int i = 1;i <= n;i++)cout << f[i] << " ";
}