LeetCode每日一题5月29日 LeetCode84.柱状图中最大矩形

短命女 2023-02-14 01:22 69阅读 0赞

## 问题描述： ##

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

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

![format_png][]

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

![format_png 1][]

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

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/largest-rectangle-in-histogram][https_leetcode-cn.com_problems_largest-rectangle-in-histogram]

**示例:**

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

## 解题思路： ##

### 1.暴力解法 ###

**给定左边界，向右遍历，依次找出最小高度，利用高\*宽，取最大值**

**下面是具体代码：**

class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
           int res = 0;
           for(int i=0;i<heights.size();i++){
               int minheight = INT_MAX;
               for(int j=i;j<heights.size();j++){
                   minheight = min(minheight,heights[j]);
                   res = max(res,minheight*(j-i+1));
               }
           }
           return res;
        }
    };

**暴力解法，有测试用例过不了**

### 2.利用单调栈 ###

**先设想，当一次遍历时，遍历到i，我们需要向左找到第一个比height\[i\]小的，向右找到第一个比height\[i\]小的元素**

**这样我们就可以求出了宽带，高度为height\[i\]取最大值**

我们创建一个**单调递增栈**

如果新的元素比栈顶元素大，就入栈

*  如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

加入这样一个规则之后，会有什么效果

*  栈内的元素是递增的
 *  当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素

举个例子，现在索引在 6 ，栈里是 1 5 6 。  
接下来新元素是 2 ，那么 6 需要出栈。  
当 6 出栈时，右边 2 代表是 6 右边第一个比 6 小的元素。

*  当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素

当 6 出栈时，5 成为新的栈顶，那么 5 就是 6 左边第一个比 6 小的元素。

下面是完整代码：

class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
           int res = 0;
           //头部和尾部插入0，是为了方便计算边界
           heights.push_back(0);
           heights.insert(heights.begin(),0);
           stack<int> stk;
           for(int i=0;i<heights.size();i++){
               while(!stk.empty()&& heights[stk.top()]>heights[i]){
                   int top = stk.top();
                   stk.pop();
                   int left = stk.top()+1;
                   int right = i-1;
                   res = max(res,heights[top]*(right-left+1));
               }
                stk.push(i);
           }
           return res;
        }
    };

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE4LzEwLzEyL2hpc3RvZ3JhbS5wbmc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE4LzEwLzEyL2hpc3RvZ3JhbV9hcmVhLnBuZw?x-oss-process=image/format,png
[https_leetcode-cn.com_problems_largest-rectangle-in-histogram]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram