单调栈

顾名思义,单调栈就是指存放有序数据的栈,分为单调递增栈和单调递减栈。

单调递增栈:栈内数据从栈底到栈顶递增
单调递减栈:站内数据从栈底到栈顶递减

单调栈的作用:可以以O(1)的平均时间复杂度一列数中,每个数的左右两边比它小的第一个数的位置。

柱状图中最大的矩形

给一列有高度的柱形,求其中面积最大的矩形。

考虑枚举有效高度,当每个柱形做为有效高度柱形来计算,即当前柱形向左一直衍生至比它低的第一个柱形,向右也是,然后这个长度诚意柱形的高度就是当前柱形为有效高度时的最大矩形。
可利用单调栈求每个柱形向左向右第一个比它低的矩形位置。

在上图中,可先把2入栈,然后扫描到1时,1比栈顶元素2小,则2向右衍生的柱形最多为1个,就是它自己。然后5,6均如栈,因为都比1大,所以1仍然能够向右继续衍生。接着到了2,5和6均要出栈,6可衍生至2,5也是衍生至2,2如栈,1可以继续向右衍生...

使用上述方法可以看出单调栈可以以O(n)的时间复杂度求出每个柱形向两边衍生的最大长度。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st1, st2;
        int n = heights.size();
        if (0==n)   return 0;
        vector<int> dp1(n), dp2(n);
        int ans = 0;
        for (int i=0; i<n; i++){
            while (!st1.empty() && st1.top()>heights[i]){
                dp2[st2.top()] = i-st2.top();
                st1.pop();  st2.pop();
            }
            st1.push(heights[i]);
            st2.push(i);
        }
        while (!st1.empty()){
            dp2[st2.top()] = n-st2.top();
            st1.pop();  st2.pop();
        }
        for (int i=n-1; i>=0; i--){
            while (!st1.empty() && st1.top()>heights[i]){
                dp1[st2.top()] = st2.top()-i;
                st1.pop();  st2.pop();
            }
            st1.push(heights[i]);
            st2.push(i);
        }
        while (!st1.empty()){
            dp1[st2.top()] = st2.top()+1;
            st1.pop();  st2.pop();
        }
        for (int i=0; i<n; i++) ans = max(ans, heights[i]*(dp1[i]+dp2[i]-1));
        return ans;
    }
};

0 条评论

发表评论

邮箱地址不会被公开。