Keshawn_lu's Blog

Leetcode 84. 柱状图中最大的矩形

字数统计: 662阅读时长: 2 min
2020/05/30 Share

题目简介:

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

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

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

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

示例:

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

思路:

首先我们得先知道对于一个矩形,它所能达到的最大面积取决于最短的那条边,所以例如上图高度为5的矩形,它要想达到以5为高度的最大面积,就必须往左右找能大于等于它高度的矩形,这样子以5为高度的矩形才能有最大的宽度。所以我们需要去找右边界与左边界。换个角度想,我们在左右两边只要找到第一个高度比5小的矩形,它们中间的矩形的高度一定都>= 5

所以问题转换为了往左右两边找第一个比目标矩阵高度小的矩形。这时我们就可以利用栈了。

遇到比栈顶元素大的值,则直接入栈;否则,此时的元素为右边界,可以先记为heights[target],开始弹出栈顶元素,直到heights[target]比栈顶元素大。

注意每次弹出的栈顶元素都是我们要的目标矩形

每次弹出一个元素时,此时的栈顶元素便是该目标矩形的左边界,即目标矩形左边第一个比它高度小的矩形;右边界我们之前已经知道了,这样子目标矩形的最大面积便为heights[top_index] * (right - left - 1),遍历时保存最大值,最后返回即可。

tips:

  • 可以在heights数组最后插入一个0,来代表末尾边界。
  • 注意在求左边界时,目标矩形无左边界的情况。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {

stack<int> st;

if(heights.size() == 0)
return 0;

int maxArea = heights[0];

heights.push_back(0); //设置末尾边界

for(int i = 0; i < heights.size(); i++){

while(!st.empty() && heights[i] < heights[st.top()]){

int top_index = st.top();

//右边第一个比heights[st.top()]小的元素
int right = i;

st.pop();
//左边第一个比heights[st.top()]小的元素
int left = st.empty() ? -1 : st.top(); //注意无左边界的情况

maxArea = max(maxArea, heights[top_index] * (right - left - 1));
}

st.push(i);
}

return maxArea;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: