https://oj.leetcode.com/problems/largest-rectangle-in-histogram/

http://blog.csdn.net/linhuanmars/article/details/20524507

public class Solution {
    public int largestRectangleArea(int[] height) 
    {
        // Solution A
        // return largestRectangleArea_Expand(height);
        
        // Solution B
        return largestRectangleArea_Stack(height);
    }
    
    ////////////////////
    // Solution A: Stack
    //
    private int largestRectangleArea_Stack(int[] h)
    {
        if (h == null || h.length == 0)
            return 0;   // invalid input
            
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0 ; i < h.length ; i ++)
        {
            while (!stack.empty() && h[i] <= h[stack.peek()])
            {
                int last = stack.pop();
                int area = 0;
                if (stack.empty())
                {
                    area = i * h[last];
                }
                else
                {
                    // 从当前栈顶元素的下一个  stack.peek() + 1到
                    // 当前下标 i (exclusive)
                    // 都比出栈元素高度大
                    area = (i - (stack.peek() + 1)) * h[last];
                }
                max = Math.max(max, area);
            }
            
            stack.push(i);
        }
        
        while (!stack.empty())
        {
            int last = stack.pop();
            int area = 0;
            if (stack.empty())
            {
                area = h.length * h[last];
            }
            else
            {
                area = (h.length - stack.peek() - 1) * h[last];
            }
            max = Math.max(max, area);
        }
        
        return max;
    }
    
    ////////////////////
    // Solution B: Expand
    //
    // 对于每一个bar i, 寻找 最左边 >= h[i] 的 index
    // 同理 找右边 
    // 计算最大
    // 
    // O(n ^ 2)
    private int largestRectangleArea_Expand(int[] h)
    {
        int max = 0;
        for (int i = 0 ; i < h.length ; i ++)
        {
            // find left
            int l = i;
            while (l >= 0 && h[l] >= h[i])
                l --;
            l++;
            
            // find right
            int r = i;
            while (r < h.length && h[r] >= h[i])
                r ++;
            r --;
            
            max = Math.max(max, h[i] * (r - l + 1));
        }
        return max;
    }
}

[LeetCode]84 Largest Rectangle in Histogram