单调栈模型整理与应用 & 经典例题

忘是亡心i 2023-01-19 08:28 7阅读 0赞

### 单调栈 ###

单调栈是指一个**栈**里所有的元素是**单调的**，单调递增（或递减）的，通过维护这个单调的栈我们可以实现许多的目的。

### 单调栈模型的应用 ###

**单调栈模型**最直接的用处是来求数组每个数的**往左第一个比他小的数**，或往右第一个比他小的数，这类问题。

我们如何来求每个数的左边第一个比它小的数呢？最简单的做法就是从i往左循环，直到找到比他小的数为止。但这样找完n个数，时间复杂度是 O ( n 2 ) O(n^2) O(n2)，有时会超时，那么我们可以用单调栈来求就可以在 O ( n ) O(n) O(n)的复杂度内求出。

**证明：** 我们可以发现第i个数左边可以作为答案的数是单调的。假设存在 a x a\_x ax和 a y a\_y ay( x < y x<y x<y并且 a x > a y a\_x>a\_y ax>ay)，那么 a x a\_x ax永远不会作为某个数的答案的，因为它右边的任意一个数 a i a\_i ai，如果 a x < a i a\_x<a\_i ax<ai的话，那么 a y < a i a\_y<a\_i ay<ai，所以 a y a\_y ay是离i最近的那个，所以 a y a\_y ay就是答案。

**做法：** 因此我们就可以用一个单调栈来放所有可能作为答案的数，然后对于每个i在这个栈里面找答案就行，然后一直维护这个单调栈即可，具体可以看下面代码模板。  
注意**初始化**！

--------------------

### 代码模板 ###

#include<iostream>
    #include<stack>
    using namespace std;
    const int N = 100010;
    
    int n,a[N],l[N];	//a存数，l[i]就是第i个数左边比他小的最近的数的位置
    stack<int> q;	//q是单调栈，存的是数的下标
    
    int main()
    { 
    	cin >> n;
    	for(int i = 1;i <= n;i++)
    		cin >> a[i];
    	a[0] = -1;		//数组的最左边一定要放一个最小值，来处理边界，这样就不要特殊处理左边界了
    	q.push(0);		//栈初始化
    	for(int i = 1;i <= n;i++)	//循环每一个数
    	{ 
    		while(a[q.top()] >= a[i])	//当栈顶元素大于等于a[i]时，他一定没法做i右边的答案了，所以就全部出队
    			q.pop();
    		l[i] = q.top();		//i的答案就是栈顶
    		q.push(i);		//i入栈
    	}
    	for(int i = 1;i <= n;i++)
    		cout << l[i] << " " << endl;	//输出每一位答案
    	return 0;
    }

--------------------

### 经典例题 ###

**模板题：**[Acwing 131： 直方图中最大的矩形][Acwing 131_]

题目大意：一堆等宽的直方图矩形，求拼成的最大面积，如图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]  
思路：外面枚举每一个矩形的高度，然后往左边找比他低的最近的位置，再往右找比他低的最近的位置，两个位置差-1就能得到矩形的宽，相乘就能得到面积，然后对每个高度计算出来的面积去max即可。

ac代码：

#include<iostream>
    #include<stack>
    using namespace std;
    const int N = 100010;
    typedef long long LL;
    
    int n,h[N],l[N],r[N];	//h存高度，l存往左边找，r往右找
    LL res;		//res找最大答案
    
    int main()
    { 
    	while(cin >> n && n)
    	{ 
    		stack<int> q;	//单调栈
    		res = 0;
    		for(int i = 1;i <= n;i++)
    			cin >> h[i];
    		h[0] = h[n+1] = -1;		//初始化处理边界
    		q.push(0);		//初始化单调栈
    		for(int i = 1;i <= n;i++)	//单调栈模板，处理左边
    		{ 
    			while(h[q.top()] >= h[i])
    				q.pop();
    			l[i] = q.top();
    			q.push(i);
    		}
    		while(q.size())		//清空栈
    			q.pop();
    		q.push(n+1);	//初始化单调栈
    		for(int i = n;i >= 1;i--)	//单调栈模板，处理右边
    		{ 
    			while(h[q.top()] >= h[i])
    				q.pop();
    			r[i] = q.top();
    			q.push(i);
    		}
    		for(int i = 1;i <= n;i++)
    			res = max(res,(LL)h[i]*(r[i]-l[i]-1));		//计算面积，求max
    		cout << res << endl;
    	}
    
    	return 0;
    }

--------------------

**经典例题：** 力扣 [5752. 子数组最小乘积的最大值][5752.]  
题目详解： [5752. 子数组最小乘积的最大值][5752. 1]

[Acwing 131_]: https://www.acwing.com/problem/content/description/133/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: /images/20221021/b8bc8c8f135a403bae490be731363237.png
[5752.]: https://leetcode-cn.com/contest/weekly-contest-240/problems/maximum-subarray-min-product/
[5752. 1]: https://blog.csdn.net/qq_45735851/article/details/116569794