Largest Rectangle in Histogram 解答

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.

histogram

Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].

histogram

The largest rectangle is shown in the shaded area, which has area = 10unit.

Example

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(n²)

 1 public class Solution {
 2     /**
 3      * @param height: A list of integer
 4      * @return: The area of largest rectangle in the histogram
 5      */
 6     public int largestRectangleArea(int[] height) {
 7         // write your code here
 8         if (height == null || height.length < 1)
 9             return 0;
10         int start, end, minHeight, result = Integer.MIN_VALUE;
11         for (start = 0; start < height.length; start++) {
12             minHeight = height[start];
13             for (end = start; end < height.length; end++) {
14                 minHeight = Math.min(minHeight, height[end]);
15                 result = Math.max(result, (end - start + 1) * minHeight);
16             }
17         }
18         return result;
19     }
20 }

Solution 2 -- Increasing Stack

根据木桶原理，面积由最矮的高度决定。我们把问题转换为

For 决定矩阵高度的那根最矮木头 i

　　看 i 往左最远能延伸到什么地方 indexLeft

　　看 i 往右最远能延伸到什么地方 indexRight

　　best = max{best, height[i] * (indexRight - indexLeft + 1)}

所以我们要找：

往左走第一个比height[i]小的数

往右走第一个比height[i]小的数

这种题典型的用递增／递减栈实现。

 1 public class Solution {
 2     /**
 3      * @param height: A list of integer
 4      * @return: The area of largest rectangle in the histogram
 5      */
 6     public int largestRectangleArea(int[] height) {
 7         // write your code here
 8         if (height == null || height.length < 1)
 9             return 0;
10         int result = 0;
11         Stack<Integer> increasingStack = new Stack<Integer>();
12         // Attention here i <= length
13         for (int i = 0; i <= height.length; i++) {
14             int currentValue = ((i == height.length) ? -1 : height[i]);
15             while (!increasingStack.isEmpty() && height[increasingStack.peek()] >= currentValue) {
16                 int currentHeight = height[increasingStack.pop()];
17                 int left = increasingStack.size() > 0 ? increasingStack.peek() : -1;
18                 int right = i;
19                 result = Math.max(result, (right - left - 1) * currentHeight);
20             }
21             increasingStack.push(i);
22         }
23         return result; 
24     }
25 }

注意，这里除了要计算以每个pop出来的元素为高的最大面积，还要计算每个未被pop出来的元素为高的最大面积。因此技巧在于最后多加一个元素-1，由于输入元素均大于等于0，所以当-1要push入栈时，栈里所有的元素都会被pop出来。

还要注意，当前值等于栈顶值时也要做出栈操作。

每个元素只入栈／出栈一次，因此时间复杂度是O(1)