引言:

单调队列和单调栈都是一种数据结构,应用十分广泛,在蓝桥杯、ICPC、CCPC等著名编程赛事都是重点的算法,今天博主将自己对单调栈与单调队列的理解以及刷题的经验,用一篇博客分享给大家,希望对大家有所帮助,它们用于解决类似“寻找最大值与最小值”这样的问题。它们的区别在于如何维护数据的单调性。、

  1. 单调栈(Monotonic Stack):

    • 单调栈是一种栈数据结构,只能在栈顶进行插入和删除操作
    • 单调栈的特点是栈中的元素按照一定的单调性排列,常用的有单调递增和单调递减。
    • 在插入新元素时,如果新元素破坏了当前的单调性,则从栈顶删除一部分元素,直到满足单调性要求。这样可以保证栈中的元素保持单调性。
    • 单调栈的典型应用是在寻找下一个更大/更小元素的问题。
  2. 单调队列(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;
}

131. 直方图中最大的矩形 - AcWing题库

#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;
}

1574. 接雨水 - AcWing题库

#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;
}

1413. 矩形牛棚 - AcWing题库

这一题之前蓝桥杯每日一题写过题解,可以看过来:AcWing 1413. 矩形牛棚(每日一题)-CSDN博客


总结:

单调栈在题目中应用很广泛,是一名算法选手所必须掌握的基础算法,在题目中遇到寻找最大最小的元素,或者对元素进行找最大最小的问题可以考虑单调栈,单调栈主要适用于一些需要找到“下一个更大(或更小)元素”的问题。通过维护一个单调递增(或递减)的栈,可以高效地找到下一个更大(或更小)元素。在实际应用中,需要注意栈的边界条件及特殊情况的处理。单调栈的时间复杂度通常为O(n),其中n为元素的个数。利用单调栈可以在题目规定的时间可以解决问题。博主在学习单调栈的过程中将自己由开始学习到逐渐理解,期间的一些疑问以及自己所收获的凝结成此篇文章,望对大家有所帮助,文章尚有不足之处,恳请各位大佬指出,感激不尽。

下一篇更新:优先队列

Logo

欢迎加入西安开发者社区!我们致力于为西安地区的开发者提供学习、合作和成长的机会。参与我们的活动,与专家分享最新技术趋势,解决挑战,探索创新。加入我们,共同打造技术社区!

更多推荐