昨天打 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
