P5788 单调栈 - 模板

题目背景

模板题，无背景。

2019.12.12 更新数据，放宽时限，现在不再卡常了。

题目描述

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

定义函数 $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)$。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_{1\dots n}$。

输出格式

一行 $n$ 个整数表示 $f(1),f(2),\dots ,f(n)$ 的值。

样例 #1

样例输入 #1

5
1 4 2 3 5

样例输出 #1

2 5 4 5 0

提示

【数据规模与约定】

对于 $30\mathrm{\%}$ 的数据，$n\le 100$；

对于 $60\mathrm{\%}$ 的数据，$n\le 5\times {10}^3$ ；

对于 $100\mathrm{\%}$ 的数据，$1\le n\le 3\times {10}^6$，$1\le a_i\le {10}^9$。

解答

#include <iostream>
#include <stack>
using namespace std;

const int N = 3e6 + 5;
int n, a[N], f[N];
stack<int> s;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;

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

    for (int i = n; i >= 1; i --) {
        while (!s.empty() && a[s.top()] <= a[i]) {
            s.pop();  // 保证当前数是栈中最小
        }

        f[i] = s.empty() ? 0 : s.top();

        s.push(i);
    }

    for (int i = 1; i <= n; i ++) {
        cout << f[i] << " ";
    }

    return 0;
}

数组模拟栈

#include <iostream>
using namespace std;

const int N = 3e6 + 5;
int n, a[N], stk[N], f[N];
int tt;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;

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

    for (int i = n; i >= 1; i --) {
        while (tt > 0 && a[stk[tt]] <= a[i]) {
            tt --;
        }

        f[i] = tt > 0 ? stk[tt] : 0;

        stk[++ tt] = i;
    }

    for (int i = 1; i <= n; i ++) {
        cout << f[i] << " ";
    }

    return 0;
}