84 Largest Rectangle in Histogram

1. Question

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area =10unit.
For example, Given heights =[2,1,5,6,2,3], return10.

2. Implementation

思路: 矩形的面积决定于宽和高,高度越高,面积可能越大,基于这样的思想,我们可以利用单调递增栈,存储有着单调递增高度的 数组index,当栈顶所存的index所对应的高度大于等于当前高度时,我们才开始计算可以得到的矩形面积。注意一个极端的情况是所给的输入高度是单调递增的,为了让stack出栈,我们在遍历输入数组时,会遍历到i等于heights.length, 并且设置curHeight为-1,因为高度一定是非负,这样就可以保证stack存储的内容最后一定会出栈
1
class Solution {
2
public int largestRectangleArea(int[] heights) {
3
Stack<Integer> stack = new Stack<>();
4
int maxArea = 0, area = 0, curHeight = 0;
5
6
for (int i = 0; i <= heights.length; i++) {
7
curHeight = i == heights.length ? -1 : heights[i];
8
9
while (!stack.isEmpty() && heights[stack.peek()] >= curHeight) {
10
int index = stack.pop();
11
area = heights[index] * (stack.isEmpty() ? i : i - stack.peek() - 1);
12
maxArea = Math.max(maxArea, area);
13
}
14
stack.push(i);
15
}
16
return maxArea;
17
}
18
}
Copied!

3. Time & Space Complexity

时间和空间都是O(n)