单调栈（C/C++）

引言：

单调队列和单调栈都是一种数据结构，应用十分广泛，在蓝桥杯、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为元素的个数。利用单调栈可以在题目规定的时间可以解决问题。博主在学习单调栈的过程中将自己由开始学习到逐渐理解，期间的一些疑问以及自己所收获的凝结成此篇文章，望对大家有所帮助，文章尚有不足之处，恳请各位大佬指出，感激不尽。

下一篇更新：优先队列