洛谷-P5788 [模板] 单调栈

题目背景

模板题，无背景。

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

题目描述

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

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

试求出 f(1…n)。

输入格式

第一行一个正整数 nn。

第二行 nn 个正整数 a_{1\dots n}a1…n。

输出格式

一行 nn 个整数 f(1\dots n)f(1…n) 的值。

输入输出样例

输入 #1

5
1 4 2 3 5

输出 #1

2 5 4 5 0

说明/提示

【数据规模与约定】

对于 30\%30% 的数据，n\leq 100n≤100；

对于 60\%60% 的数据，n\leq 5 \times 10^3n≤5×103 ；

对于 100\%100% 的数据，1 \le n\leq 3\times 10^61≤n≤3×106，1\leq a_i\leq 10^91≤ai≤109。

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int n = 3000005;
vector<int> f(n);
vector<int> sequence(n);

void monotonicStack()
{
    stack<int> s;
    for (int i = 1; i <= n; ++i) {
        if (s.empty()) 
            s.push(i);
        else {
            //注意栈里存放的是下标，所以比较的是sequence[s.top()]
            while (!s.empty() && sequence[i] > sequence[s.top()]) {
                f[s.top()] = i; s.pop(); 
            }
            s.push(i);
        }
    }
}

ostream & operator<<(ostream & os, const vector<int> & f)
{
    for (int i = 1; i <= n; ++i) os << f[i] << " ";
    os << endl;
    return os;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> sequence[i];
    monotonicStack();
    cout << f;

    return 0;
}