直方图的最大面积

1.png 2.png 3.png 4.png 5.png 6.png 7.png 8.png 9.png 10.png 11.png 12.png

public class HistogramMaxArea {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int len = heights.length;
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i < len; i++) {
            // 栈不为空并且当前遍历元素小于栈顶元素
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int high = heights[stack.peek()];
                // 将以栈顶元素为高度的元素全都出栈，结果为到达左边界
                while (!stack.isEmpty() && high == heights[stack.peek()]) {
                    stack.pop();
                }
                int width = 0;
                if (stack.isEmpty()) {
                    width = i;
                } else {
                    width = i - stack.peek() - 1;
                }
                maxArea = Math.max(maxArea, high * width);
            }
            stack.push(i);
        }

        // 已遍历完数组
        while (!stack.isEmpty()) {
            int high = heights[stack.peek()];
            while (!stack.isEmpty() && high == heights[stack.peek()]) {
                stack.pop();
            }
            int width = 0;
            if (stack.isEmpty()) {
                width = len;
            } else {
                width = len - stack.peek() - 1;
            }
            maxArea = Math.max(maxArea, width * high);
        }
        return maxArea;
    }
}