代码随想录算法训练营第六十二天| 84.柱状图中最大的矩形

代码随想录算法训练营第六十二天| 84.柱状图中最大的矩形

---

文章目录

• 代码随想录算法训练营第六十二天| 84.柱状图中最大的矩形
• • @[toc]

题目链接：84. 柱状图中最大的矩形 - 力扣（LeetCode）

题目描述：

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
1
2
3

示例 2：

输入： heights = [2,4]
输出： 4
1
2

提示：

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

用一个从栈底到栈顶非递减的栈来存放元素下标。注意这里是下标

当$heights[i]<stack.top()$ 时, 就找到了 以栈顶元素为高的矩形的面积。

其中

$矩形高度h为：当前的栈顶元素对应的高度heights[stack.top()]$

$矩形宽度w为：（当前i与栈内栈顶元素的上一个元素之差）-1$

需要比较 记录的 $ans=std::max(ans,w\ast h)$

之后将元素入栈

注意：加入给定一个非递减的数组，例如 a r r a y = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } ; array = \{1,2,3,4,5,6,7,8\}; array={1,2,3,4,5,6,7,8};

在所有元素入栈之后，均没有计算矩形面积。我们需要一个数来触发面积的计算过程。

要求这个数不大于0。

class Solution {
public:
    int largestRectangleArea(std::vector<int>& heights) {
        std::stack<int> stack;// 栈底到栈顶为 非递减
        heights.push_back(0);// 避免非递减数组出现时不运行计算答案
        int ans = 0;
        for(int i = 0;i<heights.size();i++){
            while(!stack.empty() && heights[i]<heights[stack.top()]){
                int h = heights[stack.top()];
                stack.pop();
                int w = i-(stack.empty()?-1:stack.top())-1;
                ans = std::max(ans,w*h);
            }
            stack.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18