[leetcode] Largest Rectangle in Histogram

题目：（Stack）

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.

题解：

参考http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html

难题，思路比较难想。多看看。

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int [] h = new int[height.length+1];
        int i=0;
        int result=0;
        h = Arrays.copyOf(height, height.length+1);
        while(i<h.length)
        {
            if(stack.isEmpty()||h[i]>h[stack.peek()])
               stack.push(i++);
            else
            {
                int t = stack.pop();
                result = Math.max(result, h[t]*(stack.isEmpty()? i : i-stack.peek()-1));
            }
        }
        return result;
    }
}