Algorithm Practice
Search…
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)
Last modified 2yr ago