关于单调栈（自存）
2026-10-05 18:37:02
发布于：广东
14阅读
0回复
0点赞
啥是单调栈？
顾名思义，单调栈 = 栈内元素保持严格递增 / 严格递减的栈。
两种类型：
- 单调递增栈：从栈底到栈顶，数字越来越大
- 单调递减栈：从栈底到栈顶，数字越来越小
有啥用？
快速找左边第一个比它大 / 小的元素、右边第一个比它大 / 小的元素，还有最大矩形、柱状图面积等经典题。
板子题：P49360 单调栈
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e5+10;
ll a[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<int> ans(n+1, 0);
stack<int> st;
for(int i = 1; i <=n; i++){
while(!st.empty() && a[i] > a[st.top()]){
int idx = st.top();
st.pop();
ans[idx] = i;
}
st.push(i);
}
for(int i=1;i<=n;i++) cout << ans[i] << " ";
return 0;
}
为什么可以这样实现？举例说明：
数组：[3,1,4,2]
目标：对每个数，找右边第一个比它大的值。
栈维护从底到顶递减。
- 3 入栈
[3] - 1 比栈顶 3 小，直接入栈
[3,1] - 4 来了：栈顶 1<4 → 弹出 1，1 的答案就是 4；
[3]
栈顶 3<4 → 弹出 3，3 的答案是 4；栈空，4 入栈
[4] - 2 来了：2<4，直接入栈
最后栈内剩下元素，右边没有更大的，答案记 0。
结果：[4,4,0,0]
下标：[4,4,-1,-1]
为什么是正确的，以此题为例：
我们一个元素被弹出时，当且仅当这个元素的 f[i]被放入栈，即比a[i]大的数。当我们的元素从栈中弹出的时候，肯定是它发现了第一个比它还要大的数，后续就算有数>=a[i],a[i]已经被弹出了。
这里给一张表格：
现在时间复杂度由O(n^2)变为O(n)
刷题！！！！
洛谷SP1805 HISTOGRA - Largest Rectangle in a Histogram
很标准的柱状图最大矩形
先分析，假设每个柱的高度为h[i]，我们的目标是：以 h[i] 为高，最多能向左边、向右边延伸到多远，保证区间内所有柱子高度都 ≥ h [i]。
那我们就算左边第一个高度严格小于 h [i] 的柱子下标和右边第一个高度严格小于 h [i] 的柱子下标，它中间的就是我们要的区间。
能向左延伸到：L[i]+1，能向右延伸到：R[i]-1，宽度 = R[i] - L[i] - 1，当前面积 = h[i] × (R[i] - L[i] - 1)
perfect
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 200010;
ll a[N];
int L[N], R[N];
int n;
int main(){
while(cin >> n && n != 0){
for(int i = 1; i <= n; i++){
cin >> a[i];
}
stack<int> st;
for(int i = 1; i <= n; ++i){
while(!st.empty() && a[st.top()] >= a[i])
st.pop();
if(st.empty())L[i] = 0;
else L[i] = st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n; i >= 1; --i){
while(!st.empty() && a[st.top()] >= a[i])
st.pop();
if(st.empty())R[i] = n + 1;
else R[i] = st.top();
st.push(i);
}
ll ans = 0;
for(int i = 1; i <= n; ++i){
ans=max(ans,(R[i]-L[i]-1)*a[i]);
}
cout << ans << endl;
}
return 0;
}
有帮助，赞一个