【模板】单调栈
题目描述
给出项数为 \(n\) 的整数数列 \(a_{1 \dots n}\)。
定义函数 \(f(i)\) 代表数列中第 \(i\) 个元素之后第一个大于 \(a_i\) 的元素的下标，即 \(f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}\)。若不存在，则 \(f(i)=0\)。
试求出 \(f(1\dots n)\)。
输入格式
第一行一个正整数 \(n\)。
第二行 \(n\) 个正整数 \(a_{1\dots n}\)。
输出格式
一行 \(n\) 个整数 \(f(1\dots n)\) 的值。
样例 #1
样例输入 #1
5
1 4 2 3 5
样例输出 #1
2 5 4 5 0
提示
【数据规模与约定】
对于 \(30\%\) 的数据，\(n\leq 100\)；
对于 \(60\%\) 的数据，\(n\leq 5 \times 10^3\) ；
对于 \(100\%\) 的数据，\(1 \le n\leq 3\times 10^6\)，\(1\leq a_i\leq 10^9\)。
分析
- 求每个元素右边第一个大于该元素的值的下标。
- 维护一个单调递增栈（栈顶到栈底单调递增），可以画一下下面这个图。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e6+10,INF=0x3f3f3f3f;
int n,m,a[N],ans[N],sta[N],head=0;
int main() {
// freopen("data.in", "r", stdin);
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++) {
while(head && a[sta[head]] < a[i]) {
ans[sta[head]] = i, head--;
}
sta[++head] = i;
}
for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
return 0;
}