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.

Example:
Input: [2,1,5,6,2,3]
Output: 10

Method 1. 两个循环。第一个循环把index都放到stack里面，但是遇见数字小的就及时计算前面所有数字比它大的的面积；
第二个循环处理所有剩下的的面积（stack里面是数字纯上升的index）

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights.length == 0 || heights == null) return 0;

        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;

        while(i < heights.length) {
            if(stack.empty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i);
                i++;
            }else{
                int h = heights[stack.pop()];
                int w = stack.empty()? i : i - 1 - stack.peek();
                int area = h * w;
                maxArea = Math.max(maxArea, area);
            }
        }

        while(!stack.empty()) {
            int h = heights[stack.pop()];
            int w = stack.empty()? i : i - 1 - stack.peek();
            int area = h * w;
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }
}

Method 2. 一个循环。把最后超出index的数字设为0，这样在上面方法中的第一个循环中就全部解决。

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights.length == 0 || heights == null) return 0;

        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;

        while(i <= heights.length) {
            int currH = (i == heights.length)? 0 : heights[i];
            if(stack.empty() || currH >= heights[stack.peek()]) {
                stack.push(i);
                i++;
            }else{
                int h = heights[stack.pop()];
                int w = stack.empty()? i : i - 1 - stack.peek();
                int area = h * w;
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }
}