LeetCode 84. 柱状图中最大的矩形

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]

输出：10

解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]

输出： 4

提示：

1 <= heights.length <=10^5
0 <= heights[i] <= 10^4

解法思路（参考官方题解及视频讲解）:

1、暴力1 O(n^3)

for i -> 0, n
    for j -> i, n
       (i, j) -> 最小高度，area
       update max-area

2、暴力2 O(n^2)

for i -> 0, n:
    找到 left bound, right bound
        area = height[i] * (right - left)
        update max-area

3、Stack

4、优化 Stack，加哨兵元素

法一（超时）：

class Solution {
    public int largestRectangleArea(int[] heights) {
        // Time: O(n^3)
        // Space: O(1)
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minHeight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    minHeight = Math.min(minHeight, heights[k]);
                }
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}

法二（超时）：

class Solution {
    public int largestRectangleArea(int[] heights) {
        // Time: O(n^2)
        // Space: O(1)
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}

法三：

class Solution {
    public int largestRectangleArea(int[] heights) {
        // Stack 空间换时间
        // 特殊情况1：遍历完成后，栈内元素出栈时一定可以扩展到数组的末尾
        // 特殊情况2：弹出栈顶后栈为空，一定可以扩散到数组最左边
        // 特殊情况3：栈中存在高度相等的元素，出栈
        // Time: O(n)
        // Space: O(n)
        int len = heights.length;
        if (len == 0) return 0;
        if (len == 1) return heights[0];
        int maxArea = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            // 当前元素的高度严格小于栈顶元素的高度时，出栈
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                int height = heights[stack.removeLast()];
                // 特殊情况3：栈中存在高度相等的元素，出栈
                while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                    stack.removeLast();
                }
                // 特殊情况2：弹出栈顶后栈为空，一定可以扩散到数组最左边
                int width = stack.isEmpty() ? i : (i - stack.peekLast() - 1);
                maxArea = Math.max(maxArea, width * height);
            }
            stack.addLast(i);
        }
        // 弹出栈中所有元素
        while (!stack.isEmpty()) {
            int height = heights[stack.removeLast()];
            while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                stack.removeLast();
            }
            // 特殊情况1：遍历完成后，栈内元素出栈时一定可以扩展到数组的末尾
            int width = stack.isEmpty() ? len : (len - stack.peekLast() - 1);
            maxArea = Math.max(maxArea, width * height);
        }
        return maxArea;
    }
}

优化法三：

class Solution {
    public int largestRectangleArea(int[] heights) {
        // Stack(add Sentinel)
        // Time: O(N)
        // Space: O(N)
        int len = heights.length;
        if (len == 0) return 0;
        if (len == 1) return heights[0];
        int maxArea = 0;
        int[] newHeights = new int[len + 2];
        for (int i = 0; i < len; i++) {
            newHeights[i + 1] = heights[i];
        }
        len += 2;
        heights = newHeights;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.addLast(0);
        for (int i = 1; i < len; i++) {
            while (heights[stack.peekLast()] > heights[i]) {
                int height = heights[stack.removeLast()];
                int width = i - stack.peekLast() - 1;
                maxArea = Math.max(maxArea, width * height);
            }
            stack.addLast(i);
        }
        return maxArea;
    }
}