参考 http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.html
以下摘自水中的鱼：
这样的话，就可以通过大数据。但是这个优化只是比较有效的剪枝，算法仍然是O(n*n).
想了半天，也想不出来O(n)的解法，于是上网google了一下。
如下图所示，从左到右处理直方，i=4时，小于当前栈顶（及直方3），于是在统计完区间[2,3]的最大值以后，消除掉阴影部分，然后把红线部分作为一个大直方插入。因为，无论后面还是前面的直方，都不可能得到比目前栈顶元素更高的高度了。
这就意味着，可以维护一个递增的栈，每次比较栈顶与当前元素。如果当前元素小于栈顶元素，则入站，否则合并现有栈，直至栈顶元素小于当前元素。结尾入站元素0，重复合并一次。
思路很巧妙。代码实现如下,
大数据 76ms过。
public class Solution { // O(n) using one stack public int largestRectangleArea(int[] height) { // Start typing your Java solution below // DO NOT write main() function int area = 0; java.util.Stack<Integer> stack = new java.util.Stack<Integer>(); for (int i = 0; i < height.length; i++) { if (stack.empty() || height[stack.peek()] < height[i]) { stack.push(i); } else { int start = stack.pop(); int width = stack.empty() ? i : i - stack.peek() - 1; area = Math.max(area, height[start] * width); i--; } } while (!stack.empty()) { int start = stack.pop(); int width = stack.empty() ? height.length : height.length - stack.peek() - 1; area = Math.max(area, height[start] * width); } return area; } }
[Leetcode]--Largest Rectangle in Histogram
原文：http://www.cnblogs.com/RazerLu/p/3533068.html