前言
单调栈是一种维护数组当前位置左右两侧比它小或大的最近的数的一种数据结构。
一、经典用法
单调栈的经典用法就是找数组当前位置的数左右两侧比它小或大的最近的数。
1.模板——单调栈结构(进阶)
#include<bits/stdc++.h>
using namespace std;
void findSmall(vector<int>&arr)
{
stack<int>index;
vector<vector<int> >ans(1000001,vector<int>(2,0));//存下标
int cur;
for(int i=0;i<arr.size();i++)
{
while(!index.empty()&&arr[i]<=arr[index.top()])//有重复,相等也弹出
{
cur=index.top();
index.pop();
ans[cur][0]=index.empty()?-1:index.top();
ans[cur][1]=i;
}
index.push(i);
}
while(!index.empty())
{
cur=index.top();
index.pop();
ans[cur][0]=index.empty()?-1:index.top();
ans[cur][1]=-1;
}
//有重复值就需要修正
//左侧必正确，修正右侧
//从右往左修正，n-1处必为-1，不用修正
for(int i=arr.size()-2;i>=0;i--)
{
if(ans[i][1]!=-1&&arr[ans[i][1]]==arr[i])//若相等
{
ans[i][1]=ans[ans[i][1]][1];//把右侧答案当答案
}
}
//输出
for(int i=0;i<arr.size();i++)
{
cout<<ans[i][0]<<" "<<ans[i][1]<<endl;
}
}
void solve()
{
int n;
cin>>n;
vector<int>arr(n,0);
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
findSmall(arr);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}一般题目给的数组中都包含重复的数，所以这里直接写有重复数时的单调栈模板。
首先得准备一个栈用来存下标。之后从左到右遍历数组，每次都往栈里压入当前位置的下标。
若要找比当前位置小的数，就让栈里保持严格大数压小数，否则小数压大数。当栈不为空，且当前位置的数违反了上述规则，就弹出栈顶。此时，刚刚弹出的数的左侧就是弹出后的栈顶，右侧就是当前位置的数。
当遍历结束后，只要栈不为空，还是重复上述结算规则，但此时右侧全为-1，因为已经遍历结束。
因为相等也弹出，所以对于重复的数，左侧肯定均正确，那么就去修正右侧，考虑从右往左修正。因为n-1处必为-1，所以从n-2处开始。若右侧有答案且答案和自己相等，就拿右侧答案的答案作为自己的答案。
这里的大压小和小压大可以理解为“山坡”和“山谷”，单调栈就是在一直维护这种趋势。
其实题目有的时候只用维护一侧，所以对于修正和相等时的处理还是要具体题目具体分析。
2.每日温度
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n=temperatures.size();
vector<int>ans(n,0);
stack<int>index;
int cur;
for(int i=0;i<n;i++)
{
while(!index.empty()&&temperatures[index.top()]<temperatures[i])
{
cur=index.top();
index.pop();
ans[cur]=i-cur;
}
index.push(i);
}
return ans;
}
};这个题就是一眼单调栈，而且只用维护右侧即可。
因为要找右侧比自己大的数，所以让栈保持小压大。注意相等时也压入但不结算，因为后续结算的是相隔天数，所以会自动归零。而且因为是相隔天数，所以遍历完直接结束即可。
3.子数组的最小值之和
class Solution {
public:
int MOD=1000000007;
int sumSubarrayMins(vector<int>& arr) {
int n=arr.size();
int ans=0;
stack<int>index;
int cur,left;
for(int i=0;i<n;i++)
{
while(!index.empty()&&arr[index.top()]>=arr[i])
//相等也弹出 -> 后面结算时能补回来
{
cur=index.top();
index.pop();
left=index.empty()?-1:index.top();
ans=(ans+(long long)(i-cur)*(cur-left)*arr[cur])%MOD;
}
index.push(i);
}
while(!index.empty())
{
cur=index.top();
index.pop();
left=index.empty()?-1:index.top();
ans=(ans+(long long)(n-cur)*(cur-left)*arr[cur])%MOD;
}
return ans;
}
};这个题就开始抽象起来了，更考验对题目的分析。
分析题目+联系单调栈可以发现，当找到两侧比自己小的数时，说明自己就是中间部分这段子数组中的最小值。所以，这段子数组的数量就是（自己-左侧）*（右侧-自己），最小值之和再乘以自己即可。注意相乘时的数据溢出问题。
再考虑相等的情况，举个例子，2,3,3,5,2这五个数。对于第一个3，此时左侧为2，右侧为2；对于第二个3，左侧为2，右侧为2。将两个3构成的子数组枚举出来可以发现，第二个3构成的子数组恰好包括了第一个3构成的子数组。所以，相等时选择也弹出，因为后续可以补回来。
当然，如果再分析一下题目就会发现，其实在这个题里相等时弹不弹出都一样……
4.柱状图中最大的矩形
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n=heights.size();
stack<int>index;
int cur,left;
int ans=0;
for(int i=0;i<n;i++)
{
while(!index.empty()&&heights[index.top()]>=heights[i])
//相等也弹出 -> 后面能补回来
{
cur=index.top();
index.pop();
left=index.empty()?-1:index.top();
ans=max(ans,(i-left-1)*heights[cur]);
}
index.push(i);
}
while(!index.empty())
{
cur=index.top();
index.pop();
left=index.empty()?-1:index.top();
ans=max(ans,(n-left-1)*heights[cur]);
}
return ans;
}
};这个题还是分析题目，可以发现对于每个柱子，能构成的最大矩形的高度就是左右两侧比它小的柱子分别构成的矩形面积的最大值。（好绕啊）
所以基本过程和上个题差不多，就是结算时让长度*高度取最大值。
对于相等数的处理，情况和上个题一样。
5.最大矩形
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n=matrix.size();
int m=matrix[0].size();
vector<int>height(m,0);
stack<int>index;
int cur,left;
int ans=0;
for(int i=0;i<n;i++)//以i行为底 -> 压缩数组
{
for(int j=0;j<m;j++)
{
//注意1：给的是字符，要转成数字！！
//注意2：如果是‘0’要全归零！！！！！
height[j]=matrix[i][j]=='0'?0:height[j]+1;
}
//转化 -> 柱状图最大矩形
for(int j=0;j<m;j++)
{
while(!index.empty()&&height[index.top()]>=height[j])
{
cur=index.top();
index.pop();
left=index.empty()?-1:index.top();
ans=max(ans,(j-left-1)*height[cur]);
}
index.push(j);
}
while(!index.empty())
{
cur=index.top();
index.pop();
left=index.empty()?-1:index.top();
ans=max(ans,(m-left-1)*height[cur]);
}
}
return ans;
}
};这个题就涉及到压缩数组的技巧了。对于这个矩阵，每次以第i行为底，统计高度数组，然后就可以完全当作上一题来处理了。注意若矩阵来到0，则高度数组要更新为0而非加0！
二、通用用法
将经典用法进行推广，单调栈其实是在维护求解答案的可能性。栈中所有的元素会按单调性进行组织，并每次弹出对求解后续答案无帮助的值。（我在写这篇文章时也没太懂这段话的意思TvT）总之就是，当出现“下一个最值”或“上一个最值”类似的意思时，就可以考虑使用单调栈。跟前几个算法一样，分析题目单调性很重要！！！
1.最大宽度坡
class Solution {
public:
int maxWidthRamp(vector<int>& nums) {
int n=nums.size();
stack<int>index;
index.push(0);
int ans=0;
for(int i=1;i<n;i++)
{
if(nums[index.top()]>nums[i])
{
index.push(i);
}
}
for(int i=n-1;i>=0;i--)
{
while(!index.empty()&&nums[index.top()]<=nums[i])
{
ans=max(ans,i-index.top());
index.pop();
}
}
return ans;
}
};上来就来个猛的，这个题的单调性确实很难分析……
因为相当于要找左侧小于等于当前位置的最远的数，所以考虑用单调栈来维护所有可能的左侧位置，即，遇到比当前栈顶小的数就入栈。之后从右往左遍历，只要栈不为空，且栈顶的数小于等于当前位置的数，就结算答案并弹出。
至于为什么这个方法可以，举个例子，对于3,2,3,4,1这组数，统计出来的单调栈为3,2,1，所以即使2,3和2,3,4可以构成“坡”，但由于2的左侧还有一个3可以和4构成更大的坡，所以没必要结算。所以，为了在入栈时就确保后续从右往左遍历时距离最远，只建立单调递减的栈即可。
此时，单调栈维护的就是最大宽度可能由哪些位置参与的可能性。
2.去除重复字母
class Solution {
public:
string removeDuplicateLetters(string s) {
int n=s.length();
map<char,int>cnt;
for(int i=0;i<n;i++)
{
cnt[s[i]]++;
}
stack<int>index;
vector<bool>enter(26,false);
for(int i=0;i<n;i++)
{
if(!enter[s[i]-'a'])
{
while(!index.empty()&&s[index.top()]>s[i]&&cnt[s[index.top()]]>0)
{
enter[s[index.top()]-'a']=false;
index.pop();
}
index.push(i);
enter[s[i]-'a']=true;
}
cnt[s[i]]--;
}
string ans;
while(!index.empty())
{
ans+=s[index.top()];
index.pop();
}
for(int i=0;i<ans.length()/2;i++)
{
char t=ans[i];
ans[i]=ans[ans.length()-i-1];
ans[ans.length()-i-1]=t;
}
return ans;
}
};这个题就更抽象了，整个题目对单调性的提示在我看来也就“字典序”这一处……
首先建立一个map存放字母的出现次数。之后还要建立一个数组用来表示字母是否入过栈。
然后开始遍历，每次让出现次数减1。只有当字母没入过栈时才考虑结算，结算时只要栈不为空且当前字母的字典序比栈顶更小，且栈顶字母在后续还会出现时，才会弹出，之后压入当前字母。这里注意，若栈顶字母后续不会出现了，就不管字典序依然压入当前字母！
最后栈中的元素从底到顶就是答案字符串。
3.大鱼吃小鱼
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>&fish)
{
int n=fish.size();
stack<pair<int,int>>index;
int ans=0;
for(int i=n-1,curTurns;i>=0;i--)//同时吃自己右边->从右往左吃
{
curTurns=0;
while(!index.empty()&&fish[index.top().first]<fish[i])
{
curTurns=max(curTurns+1,index.top().second);
index.pop();
}
index.push(make_pair(i,curTurns));
ans=max(ans,curTurns);
}
return ans;
}
void read()
{
int n;
cin>>n;
vector<int>fish(n,0);
for(int i=0;i<n;i++)
{
cin>>fish[i];
}
cout<<solve(fish);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
read();
return 0;
}这个题的单调性就比较明显，但相对的求解过程就不是很好想了。
首先这个题的难点个人认为在这个“操作”的设定上，这b鱼可以连着吃是最难模拟的。所以换个角度，将鱼连续吃看作一个区间内从右向左吃就好。举个例子，3,2,1,2这四条鱼，可以吃的区间为前三条3,2,1，所以将连续吃的过程看作从右向左吃，即2先吃1，然后3再吃2，这样这个区间就结束了，然后就是剩3,2，所以最后3吃2，一共两步。
想明白这个就好写很多了。首先考虑栈中压入的是一个pair，分别是下标和对应轮数。之后为了模拟从右往左吃，就从右往左遍历数组，每次压入当前鱼位置和吃到最后的轮数，并统计答案。当栈不为空，且自己比右侧鱼大时，即可以吃，就统计轮数。轮数的统计是，自己当前的轮数+1和被吃鱼的轮数的最大值，比如4,3,2,2,2这个数组，3能吃后面三条，轮数为3。所以当4向右吃时，先吃3，轮数为1，之后可以看作4等3吃完后面的鱼再吃3，所以轮数为max（1+1，3）=3。
4.统计全 1 子矩形
class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int n=mat.size();
int m=mat[0].size();
//压缩数组
vector<int>height(m,0);
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
height[j]=mat[i][j]==0?0:height[j]+mat[i][j];
}
stack<int>index;
int cur,left,down,len;
for(int i=0;i<m;i++)
{
while(!index.empty()&&height[index.top()]>=height[i])
{
cur=index.top();
index.pop();
if(height[cur]>height[i])//相等弹出但不结算
{
left=index.empty()?-1:index.top();
len=i-left-1;
down=max(left==-1?0:height[left],height[i])+1;
ans+=(height[cur]-down+1)*len*(len+1)/2;
}
}
index.push(i);
}
while(!index.empty())
{
cur=index.top();
index.pop();
left=index.empty()?-1:index.top();
len=m-left-1;
down=(left==-1?0:height[left])+1;
ans+=(height[cur]-down+1)*len*(len+1)/2;
}
}
return ans;
}
};首先上来看到这个形式就可以考虑压缩数组。之后就可以转化成求对应柱状图的全1子矩形。
之后思考统计方法，对于每个柱子，其能构成的全1子矩形的高度就是左右两侧比自己小的高度最大值+1~自己的高度。再考虑长度方面，对于每个高度，长度的范围都是1~左右间隔。所以可以发现长度的种类数呈一个从1到间隔，公差为1的等差数列，可以用求和公式。所以最终公式就是可能的高度数量*可能的长度数量。
再就是相等时，弹出但不结算，交给后续结算。
总结
归根结底最重要的还是对题目单调性的分析，再结合对单调栈的理解才行……