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.
难度：94. 参考了网上各种解法，归纳如下：
解法一：brute force的方法很直接，就是对于每一个窗口，找到其中最低的高度，然后求面积，去其中最大的矩形面积。总共有n^2个窗口，找最低高度是O(n)的操作，所以复杂度是O(n^3)。
解法二：就是从每一个bar往两边走，以自己的高度为标准，直到两边低于自己的高度为止，然后用自己的高度乘以两边走的宽度得到矩阵面积。因为我们对于任意一个bar都计算了以自己为目标高度的最大矩阵，所以最好的结果一定会被取到。每次往两边走的复杂度是O(n)，总共有n个bar，所以时间复杂度是O(n^2)。
解法三：在网上发现另外一个使用一个栈的O(n)解法，代码非常简洁，栈内存储的是高度递增的下标。对于每一个直方图高度，分两种情况。1：当栈空或者当前高度大于栈顶下标所指示的高度时，当前下标入栈。否则，2：当前栈顶出栈，并且用这个下标所指示的高度计算面积。而这个方法为什么只需要一个栈呢？因为当第二种情况时，for循环的循环下标回退，也就让下一次for循环比较当前高度与新的栈顶下标所指示的高度，注意此时的栈顶已经改变由于之前的出栈。
这种方法其实是第二种方法的变体，因为其实我们对于任何一个bar都计算了以自己为目标高度的最大矩阵，只是因为有了栈的引入，我们能够立即知道自己两边低于自己高度的bar的坐标，节省了两边走的复杂度O（N）
实现中注意最后还要对剩下的栈做清空并且判断，因为算法中每次是对于前面的元素面积进行判断，所以循环结束中如果栈中仍有元素，还是要继续维护面积直到栈为空。
这道题思路还是比较绕的，要仔细想想才能理清。不过解法确实很简练，总共只需要扫描一遍，所以时间复杂度是O(n)，空间复杂度是栈的大小，最坏情况是O(n)。
1 public class Solution { 2 public int largestRectangleArea(int[] height) { 3 if (height == null || height.length == 0) { 4 return 0; 5 } 6 LinkedList<Integer> stack = new LinkedList<Integer>(); 7 int area = 0; 8 for (int i=0; i<height.length; i++) { 9 if (stack.size()==0 || height[stack.peek()]<height[i]) { 10 stack.push(i); 11 } 12 else { 13 int temp = stack.pop(); 14 int width = (stack.size()==0)? i : i-stack.peek()-1; 15 area = Math.max(area, height[temp]*width); 16 i--; 17 } 18 } 19 while (stack.size()!=0) { 20 int temp = stack.pop(); 21 int width = (stack.size()==0)? height.length : height.length-stack.peek()-1; 22 area = Math.max(area, height[temp]*width); 23 } 24 return area; 25 } 26 }
Leetcode: Largest Rectangle in Histogram
原文：http://www.cnblogs.com/EdwardLiu/p/3985311.html