昨天打 AT 碰到了一道单调栈的题，于是来复习一下
单调栈
栈内元素单调性
有单调递增栈 和 单调递减栈
实现：
举个例子：
假设入栈序列为
1 4 2 8 9 3
要模拟一个单调递增栈：
- \(i=1\) 时，栈为空，\(1\) 入栈后仍然保持单调性，将 \(1\) 入栈；
- \(i=2\) 时，栈顶元素为 \(1\)，\(4\) 入栈后仍然保持单调性，将 \(4\) 入栈；
- \(i=3\) 时，栈顶元素为 \(4\)，\(2\) 入栈后不满足单调性，\(4\) 出栈。
此时 \(2\) 入栈后能保持单调性，\(2\) 入栈； - \(i=4\) 时，栈顶元素为 \(2\)，\(8\) 入栈后仍然保持单调性，将 \(8\) 入栈；
- \(i=5\) 时，栈顶元素为 \(8\)，\(9\) 入栈后仍然保持单调性，将 \(9\) 入栈；
- \(i=6\) 时，栈顶元素为 \(9\)，\(3\) 入栈后不满足单调性，\(9\)出栈。
这时栈顶元素为 \(8\)，\(3\) 入栈后不满足单调性，\(8\)出栈。
此时 \(3\) 入栈后能保持单调性，\(3\) 入栈；
代码：
stack<int>st;//栈里面存下标
for(int i=1;i<=n;i++)
{
while(!st.empty()&&a[st.top()]>a[i])//a[i]入栈后不是单调递增的
st.pop();//出栈
……//更新答案
st.push(i);
}
那它有什么用呢？
题目大意：
给你一个数列 \(a\)，求数列中第 \(i\) 个元素后面第一个大于它的元素的下标
思路：
- 思路一：建立一个单调递减的栈
按照顺序入栈
如果一个数入栈就不满足单调递减了，证明这个数是目前栈顶的元素后面第一个大于它的元素的下标
记录答案 - 思路二：建立一个单调递减的栈
倒序入栈
如果一个数入栈就不满足单调递减了，栈顶出栈
最后栈顶就是此时入栈元素后面第一个大于它的元素的下标
记录答案
完整代码：
思路一：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[3000100];
int f[3000100];
stack<int>st;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
while(!st.empty()&&a[st.top()]<a[i]){
f[st.top()]=i;
st.pop();
}
st.push(i);
}
for(int i=1;i<=n;i++)
{
cout<<f[i]<<(i!=n?" ":"\n");
}
return 0;
}
思路二：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[3000100];
stack<int>st;
int f[3000100];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=n;i>=1;i--)
{
while(!st.empty()&&a[st.top()]<=a[i]) st.pop();
if(!st.empty())f[i]=st.top();//这里要特别判断一下是否为空
else f[i]=0;
st.push(i);
}
for(int i=1;i<=n;i++)
{
cout<<f[i]<<(i!=n?" ":"\n");
}
return 0;
}
例题：
https://www.luogu.com.cn/problem/P2866
https://www.luogu.com.cn/problem/P2947
https://atcoder.jp/contests/abc372/tasks/abc372_d