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 = 10
unit.
Given height = [2,1,5,6,2,3]
,
return 10
.
Solution 1 -- Naive
For each start point i
For each end point j
minHeight = min height between i and j
result = max{result, (j - i + 1) * minHeight}
Time Complexity O(n2)
public class Solution {
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
public int largestRectangleArea(int[] height) {
// write your code here
if (height == null || height.length < 1)
return 0;
int start, end, minHeight, result = Integer.MIN_VALUE;
for (start = 0; start < height.length; start++) {
minHeight = height[start];
for (end = start; end < height.length; end++) {
minHeight = Math.min(minHeight, height[end]);
result = Math.max(result, (end - start + 1) * minHeight);
}
}
return result;
}
}
Solution 2 -- Increasing Stack
根据木桶原理,面积由最矮的高度决定。我们把问题转换为
For 决定矩阵高度的那根最矮木头 i
看 i 往左最远能延伸到什么地方 indexLeft
看 i 往右最远能延伸到什么地方 indexRight
best = max{best, height[i] * (indexRight - indexLeft + 1)}
所以我们要找:
往左走第一个比height[i]小的数
往右走第一个比height[i]小的数
这种题典型的用递增/递减栈实现。
public class Solution {
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
public int largestRectangleArea(int[] height) {
// write your code here
if (height == null || height.length < 1)
return 0;
int result = 0;
Stack<Integer> increasingStack = new Stack<Integer>();
// Attention here i <= length
for (int i = 0; i <= height.length; i++) {
int currentValue = ((i == height.length) ? -1 : height[i]);
while (!increasingStack.isEmpty() && height[increasingStack.peek()] >= currentValue) {
int currentHeight = height[increasingStack.pop()];
int left = increasingStack.size() > 0 ? increasingStack.peek() : -1;
int right = i;
result = Math.max(result, (right - left - 1) * currentHeight);
}
increasingStack.push(i);
}
return result;
}
}
注意,这里除了要计算以每个pop出来的元素为高的最大面积,还要计算每个未被pop出来的元素为高的最大面积。因此技巧在于最后多加一个元素-1,由于输入元素均大于等于0,所以当-1要push入栈时,栈里所有的元素都会被pop出来。
还要注意,当前值等于栈顶值时也要做出栈操作。
每个元素只入栈/出栈一次,因此时间复杂度是O(1)