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.
For example,
Given height = [2,1,5,6,2,3],
return 10.
https://oj.leetcode.com/problems/largest-rectangle-in-histogram/
思路1：穷举左右边界，O(n^2)，太慢。
思路2：解法见参考2。复杂度 O(n)。
该算法正确的原因：详见参考1，我的理解大概是这样：我们要做的是，对于任意的一个bar ‘x‘，我们需要计算以x为高度能形成的最大矩形。为了计算以x为高度的最大矩形，我们需要找到左边第一个比x矮的位置和右边一的哥比x矮的位置来计算这个矩形的宽度。对于这个用stack的巧妙解法，当遇到递减的bar时，我们pop并计算以这个bar为高度的最大矩形，遇到的递减的bar就是右边界，而左边界就是栈顶的元素。
public class Solution { public int largestRectangleArea(int[] height) { Stack<Integer> stack = new Stack<Integer>(); int maxArea = 0; for (int i = 0; i < height.length;) { if (stack.isEmpty() || height[i] >= height[stack.peek()]) { stack.push(i++); } else { int start = stack.pop(); int width = stack.isEmpty() ? i : (i - stack.peek() - 1); maxArea = Math.max(maxArea, height[start] * width); } } while (!stack.isEmpty()) { int start = stack.pop(); int width = stack.isEmpty() ? height.length : (height.length - stack.peek() - 1); maxArea = Math.max(maxArea, height[start] * width); } return maxArea; } public static void main(String[] args) { System.out.println(new Solution().largestRectangleArea(new int[] { 2, 1, 5, 6, 2, 3 })); } }
参考：
http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html#2973562
http://blog.csdn.net/linhuanmars/article/details/20524507
[leetcode] Largest Rectangle in Histogram,布布扣,bubuko.com
[leetcode] Largest Rectangle in Histogram
原文：http://www.cnblogs.com/jdflyfly/p/3815756.html
