【算法与数据结构】——单调栈

拼搏现实的明天。 2022-08-31 09:45 24阅读 0赞

# 单调栈 #

## 定义 ##

单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大  
单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小

## 实现 ##

就是将要入栈的元素与栈顶元素作比较，如果是递增栈，就将栈顶比要入栈的元素大的元素弹出，然后将元素入栈。递减栈类似。

## 代码 ##

递增栈

stack<int> st;
    //此处一般需要给数组最后添加结束标志符
    for (遍历这个数组)
    { 
    	if (栈空 || 栈顶元素小于等于当前比较元素)
    	{ 
    		入栈;
    	}
    	else
    	{ 
    		while (栈不为空 && 栈顶元素大于当前元素)
    		{ 
    			栈顶元素出栈;
    			更新结果;
    		}
    		当前数据入栈;
    	}
    }

单调栈代码和思路看起来很简单，用起来却可以解决很多奇妙的问题。接下来看两个例题。

# 例题 #

1.  柱状图中的最大矩形  
    [题目地址][Link 1]  
    给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]  
思路：  
利用单调递增栈实现，同时为每一个矩形记录前后比他高的矩形数量，放在另一个栈中，每一个矩形高度入栈时，前面弹出的元素就是矩形左面比他高的矩形，需要记录数量，如果没有弹出元素，数量记为1，矩形高度出栈时，在他前面出栈的元素数量就表示，矩形右边比他高的矩形数量。  
AC代码：

#include <iostream>
    #include <bits/stdc++.h>
    #define maxn int(1e5+1)
    using namespace std;
    int heights[maxn];
    int main()
    { 
        cin.sync_with_stdio(0);
        cin.tie(0);
        int n;
        cin >> n;
        while(n)
        { 
            for(int i = 0;i < n;i++)
            { 
                cin >> heights[i];
            }
            stack<int> height;
            stack<int> cnt;
            long long res = 0;
            long long c = 0;
            for(int i = 0;i < n;i++)
            { 
                c = 0;
                while(!height.empty()&&heights[i] < height.top())
                { 
                    c += cnt.top();
                    if((c * height.top()) > res)
                    { 
                        res = (c * height.top());
                    }
                    cnt.pop();
                    height.pop();
                }
                c++;
                cnt.push(c);
                height.push(heights[i]);
            }
            c = 0;
            while(!height.empty())
            { 
                c += cnt.top();
                if((c * height.top())>res)
                { 
                    res = (c * height.top());
                }
                cnt.pop();
                height.pop();
            }
            cout << res << endl;
            cin >> n;
        }
    
        return 0;
    }

1.  最大子矩阵问题  
    [1008][]  
    这个题目我有整理在[【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（1）][2021_MINIEYE_1]  
    思路与求矩形面积的类似。只不过是这个要遍历整个矩阵，同时要对矩阵做一些处理。
2.  求最大区间  
    描述：给出一组数字，求一区间，使得区间元素和乘以区间最小值最大，结果要求给出这个最大值和区间的左右端点  
    输入：3 1 6 4 5 2  
    输出：60  
           3 5  
    解释：将3到5（6+4+5）这段区间相加，将和与区间内最小元素相乘获得最大数字60  
    思路：使用暴力解法求出所有区间，再求出区间的最小值相乘更新数据。  
    使用一个单调递减栈采用类似最大矩形面积的思想，找到一个元素前后所有比他大的元素做计算即可。

int GetMaxSequence(vector<int>& v)
    { 
    	stack<int> st;
    	vector<int> vs(v.size()+1);
    	vs[0] = 0;
    	for (int i = 1; i < vs.size(); i++)
    	{ 
    			vs[i] = vs[i - 1] + v[i-1];
    	}
    	v.push_back(-1);
    	int top, start, end, ret = 0;
    	for (int i = 0; i < v.size(); i++)
    	{ 
    		if (st.empty() || v[st.top()] <= v[i])
    		{ 
    			st.push(i);
    		}
    		else
    		{ 
    			while (!st.empty() && v[st.top()] > v[i])
    			{ 
    				top = st.top();
    				st.pop();
    				int tmp = vs[i] - vs[top];
    				tmp = tmp * v[top];
    				if (tmp > ret)
    				{ 
    					ret = tmp;
    					start = top+1;
    					end = i;
    				}
    			}
    			st.push(top);
    			v[top] = v[i];//与第二题相同的道理，将当前数据的更改最左的top下标，防止出现比当前数据更小的数据
    			//这句在这道题里真的超级难理解，但是只要你有耐心相信你可以理解的
    		}
    	}
    	return ret
    }

[Link 1]: https://acm.hdu.edu.cn/showproblem.php?pid=1506
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]: /images/20220829/c1a0dc8707e2496aa213707355c96db8.png
[1008]: https://acm.hdu.edu.cn/showproblem.php?pid=6957
[2021_MINIEYE_1]: https://blog.csdn.net/qq_45488453/article/details/119023116