84. 柱状图中最大的矩形

84. 柱状图中最大的矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        } else if (len == 1) {
            return heights[0];
        }
        int[] newHeigths = new int[len + 2];
        for (int i = 0; i < heights.length; i++) {
            newHeigths[i + 1] = heights[i];
        }
        heights = newHeigths;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        int area = 0;
        for (int i = 1; i < heights.length; i++) {
            while (heights[i] < heights[stack.peek()]) {
                // 当前遍历到的严格小于栈顶的 
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                area = Math.max(area, width * height);
            }
            stack.push(i);
        }
        return area;
    }
}