LeetCode84 柱状图中最大的矩形

LeetCode84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1
求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

题目链接：
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

暴力解法

依次遍历柱形的高度，对于每一个高度的柱子开始，用left，right向两侧延伸，直到遇到高度小于heights[i]的柱子，就确定了矩形的左右边界，求出以当前高度为矩形的最大宽度多少，矩形的面积公式为S = 底×高 = (right - left + 1) × heights[i]

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        int left, right, maxid = 0, len = heights.size();
        if(len == 0)
            return 0;
        for(int i=0; i<len; i++){
    
            left = i;
            right = i;
            while(left>0 && heights[left - 1] >= heights[i]) left--; //向左找左边界
            while(right<len-1 && heights[right + 1] >= heights[i]) right++; //向右找右边界
            int wide = (right - left + 1);
            maxid = max(maxid, wide * heights[i]);
        }
        return maxid;
    }
};

单调栈

单调栈模板
从左向右遍历序列的同时构建单调栈，若第i个位置的heights[i]比栈顶的元素要矮，可以直接把栈顶的元素pop掉，因为之后的计算都不再需要这么高，矩形的高是受限于次高的那个

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        if(heights.size()==0)
            return 0;
        int len = heights.size(), max = 0;
        stack<int> s;
        for(int i=0; i<len; i++){
    
            //构建非单调递减的栈
            while(!s.empty() && heights[s.top()] > heights[i]){
    
                int key = s.top(), right = i;
                s.pop();
                if(!s.empty())
                    heights[key] = heights[key] * (right - s.top() - 1);
                else
                    heights[key] = heights[key] * right;
                max = max > heights[key] ? max : heights[key];
            }
            s.push(i);
        }
        //一次遍历完成以后，需考虑将栈里剩余的元素全部出栈
        if(!s.empty()){
    
            int right = s.top();
            while(!s.empty()){
    
                int key = s.top();
                s.pop();
                if(!s.empty())
                    heights[key] = heights[key] * (right - s.top());
                else
                    heights[key] = heights[key] * (right + 1);
                max = max > heights[key] ? max : heights[key];
            }
        }
        return max;
    }
};

· 若不想遍历完数组后还要处理栈里剩余的元素(eg:数组内的都是递增的，这时遍历完整个数组就只有入栈操作，没有出栈操作，可以在序列末尾添加一个高度为0的元素，这样可以将前面的元素都pop()出来，因为添了个0后整个序列不再满足单调递增的原则）。这种方法叫[哨兵法]，就是在右侧添加一个小于数组中最小值的项即可。

· 在数组前添加一个零，当栈中只有一个有效数据时，s.pop()完后，在获取矩形宽的时候，s.top()就会报错，除非多加if-else判断语句，而加了0之后，就不需要if-else操作。

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        if(heights.size()==0)
            return 0;
        heights.insert(heights.begin(), 0); //在序列前端插入一个高为0的数据
        heights.push_back(0); //在序列尾部添加一个高为0的数据
        int len = heights.size(), maxid = 0;
        stack<int> s;
        for(int i=0; i<len; i++){
    
            //构建非单调递减的栈
            while(!s.empty() && heights[s.top()] > heights[i]){
    
                int key = s.top(), right = i;
                s.pop();
                heights[key] = heights[key] * (right - s.top() - 1);
                maxid = max(maxid, heights[key]);
            }
            s.push(i);
        }
        return maxid;
    }
};

参考的链接（这篇文章所使用的图片完全都是出自于该链接的作者）：
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/