阅读量:0
引言：
单调队列和单调栈都是一种数据结构，应用十分广泛，在蓝桥杯、ICPC、CCPC等著名编程赛事都是重点的算法，今天博主将自己对单调栈与单调队列的理解以及刷题的经验，用一篇博客分享给大家，希望对大家有所帮助，它们用于解决类似“寻找最大值与最小值”这样的问题。它们的区别在于如何维护数据的单调性。、
单调栈（Monotonic Stack）：
- 单调栈是一种栈数据结构，只能在栈顶进行插入和删除操作。
- 单调栈的特点是栈中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
- 在插入新元素时，如果新元素破坏了当前的单调性，则从栈顶删除一部分元素，直到满足单调性要求。这样可以保证栈中的元素保持单调性。
- 单调栈的典型应用是在寻找下一个更大/更小元素的问题。
单调队列（Monotonic Queue）：
- 单调队列是一个双端队列，支持在队列两端进行插入和删除操作。
- 单调队列的特点是队列中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
- 在插入新元素时，如果新元素破坏了当前的单调性，则在队尾删除一部分元素，直到满足单调性要求。这样可以保证队列中的元素保持单调性。
- 单调队列的典型应用是在滑动窗口中寻找最大/最小值的问题。
单调队列和单调栈都是用于维护数据的单调性，但单调队列是双端队列，用于在滑动窗口中寻找最大/最小值，而单调栈是栈数据结构，用于寻找下一个更大/更小元素。
下面我们对单调栈进行深度解析
单调栈：
单调栈是一种数据结构，通常用于解决一些与序列相关的问题，特别是在需要找到元素在序列中的「下一个更大元素」或「下一个更小元素」的情况下。单调栈可以用于在线性时间复杂度内解决这些问题。
单调栈分为单调递增栈和单调递减栈两种类型：
1.单调递增栈：
栈中元素从栈底到栈顶递增。在处理序列时，当遇到一个元素时，如果该元素比栈顶元素大，就可以将栈顶元素出栈，直到栈为空或者栈顶元素大于等于当前元素。这样，栈中的元素就是在当前元素之前且比当前元素小的元素。
2.单调递减栈：
栈中元素从栈底到栈顶递减。在处理序列时，当遇到一个元素时，如果该元素比栈顶元素小，就可以将栈顶元素出栈，直到栈为空或者栈顶元素小于等于当前元素。这样，栈中的元素就是在当前元素之前且比当前元素大的元素。
使用单调栈的一般步骤如下：
1.创建一个空栈。
2.遍历待处理的序列，对于每个元素执行以下操作：
1.如果当前元素比栈顶元素大（或小，取决于是递增栈还是递减栈），则持续将栈顶元素出栈，直到栈为空或者栈顶元素满足某种条件（例如比当前元素大或小）。
2.记录弹出的元素，说明他是单调递减栈或单调递增栈第一个不满足的元素，可以在此元素根据题意进行操作
3.如果栈不为空，比较当前元素与栈顶元素的大小：
4..将当前元素入栈。
单调栈常用于解决一些数组或序列相关的问题，如找到下一个更大元素、下一个更小元素。
模板奉上：
第一种使用stack
stack<int> st; // 单调栈，存储元素的下标 nums[n]=-1; //多加一个-1元素，防止到最后栈中还是单调递增栈，未能更新最大值 //单调递减栈就是nums[n]=0x3f3f3f; for (int i = 0; i < n; i++) { while (!st.empty() && nums[i] <= nums[st.top()]) {//不满足单调递增栈，就开始更新 res[st.top()] = i; // 弹出元素直到满足单调递增 st.pop(); } st.push(i);//下标入队 }
第二种手写一个单调栈
int work3(int h[]) { // stk 从下标 1 开始存储 int top = 0, res = 0; // 遍历到 m + 1 的位置 // 因为是在出栈时统计，为保证遍历结束时所有下标都会被统计，默认 m + 1 位置存储 0 for (int i = 1; i <= m + 1; ++ i ) { while (top && h[stk[top]] >= h[i]) { int l = stk[top -- ]; //此处添加代码根据题意进行操作 } stk[ ++ top] = i; } return res; }
实战演练——单调栈练习题
#include<iostream> #include<stack> using namespace std; int n; const int N=3e6+5; int a[N],res[N]; stack<int> stk; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=n;i>=1;i--){ while(!stk.empty()&&a[stk.top()]<=a[i]){ stk.pop(); } res[i]=stk.empty()?0:stk.top(); stk.push(i); } for(int i=1;i<=n;i++){ cout<<res[i]<<" "; } return 0; }#include<iostream> #include<stack> using namespace std; typedef long long ll; const int N=1e5+5; int n; ll a[N]; ll res; int main(){ while(cin>>n&&n){ for(int i=0;i<n;i++){ cin>>a[i]; } a[n]=-1;//单调递增栈，不要忘记最后一个赋值为-1，不然跟上图里面的数据不会更新 res=0; stack<int> st;//使用STL的stack for(int i=0;i<=n;i++){ while(!st.empty()&&a[st.top()]>=a[i]){//每当不符合说明要开始更新最大面积了 int index=st.top();//每次弹出来跟当前不满足的值进行计算最大面积 st.pop(); int l=st.empty()?-1:st.top(); res=max(res,(i-l-1)*a[index]);//i-l-1为宽，a[index]为高 } st.push(i);//下标入栈 } cout<<res<<endl; } return 0; }#include<iostream> #include<stack> using namespace std; const int N=1e5+5; int n; int a[N]; int ans; stack<int> st; int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } //由于寻找第一个右边比他大的元素，为单调递减栈，不需要再加一个-1，此题边界不可以接雨水，所以不用赋值最后一位 for(int i=0;i<n;i++){ while(!st.empty()&&a[st.top()]<a[i]){//当前值大于栈顶元素，开始更新雨水面积 int dex=st.top(); st.pop(); int left=st.empty()?i-1:st.top();//i-1与上题不同具体问题具体分析，此题若栈中没有元素，自己自成一个，不可能接住水与下面(i-left-1)，left带入为计算0 int h=min(a[left],a[i])-a[dex];//高度 ans+=h*(i-left-1); } st.push(i); } cout<<ans<<endl; return 0; }这一题之前蓝桥杯每日一题写过题解，可以看过来：AcWing 1413. 矩形牛棚（每日一题）-CSDN博客
总结：
单调栈在题目中应用很广泛，是一名算法选手所必须掌握的基础算法，在题目中遇到寻找最大最小的元素，或者对元素进行找最大最小的问题可以考虑单调栈，单调栈主要适用于一些需要找到“下一个更大（或更小）元素”的问题。通过维护一个单调递增（或递减）的栈，可以高效地找到下一个更大（或更小）元素。在实际应用中，需要注意栈的边界条件及特殊情况的处理。单调栈的时间复杂度通常为O(n)，其中n为元素的个数。利用单调栈可以在题目规定的时间可以解决问题。博主在学习单调栈的过程中将自己由开始学习到逐渐理解，期间的一些疑问以及自己所收获的凝结成此篇文章，望对大家有所帮助，文章尚有不足之处，恳请各位大佬指出，感激不尽。
下一篇更新：优先队列
