84.Largest Rectangle in Histogram

1- Stack - O(n）

难想

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int ans = 0;
        for(int i = 0; i < heights.length; i++){
            while(stack.peek() != -1 && heights[stack.peek()] >= heights[i]){
                ans = Math.max(ans, heights[stack.pop()] * (i - 1 - stack.peek()));
            }
            stack.push(i);
        }
        while(stack.peek() != -1){
            ans = Math.max(ans, heights[stack.pop()] * (heights.length - 1 - stack.peek()));
        }
        return ans;
    }
}