Problem_84. Largest Rectangle in Histogram - xwu36/LeetCode GitHub Wiki

Explanation:
Use stack to store the value and index pair.
if the current value is greater than the value of the top element on the stack, 
push the current value onto the stack.
otherwise
pop out the elements from the stack whose values are greater than the current element,
and update the current element index to be the index of the last element popped out from the stack

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if(n == 0)
            return 0;
        Stack<int[]> stack = new Stack<int[]>();
        int max = 0;
        for(int i = 0; i <= n; i++){
            int h = i == n ? 0 : heights[i];
            if(stack.empty() || stack.peek()[0] < h){
                stack.push(new int[]{h, i});
            }else{
                int index = i;
                while(!stack.empty() && stack.peek()[0] > h){
                    int[] cur = stack.pop();
                    index = cur[1];
                    max = Math.max(max, cur[0] * (i - cur[1]));
                }
                stack.push(new int[]{h, index});
            }
        }
        return max;
    }
}