84. 柱狀圖中最大的矩形

給定?n?個(gè)非負(fù)整數(shù)，用來表示柱狀圖中各個(gè)柱子的高度。每個(gè)柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例 1:

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

輸出：10

解釋：最大的矩形為圖中紅色區(qū)域，面積為 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、優(yōu)化 Stack，加哨兵元素

?法一（超時(shí)）：

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;
    }
}

法二（超時(shí)）：

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 空間換時(shí)間
        // 特殊情況1：遍歷完成后，棧內(nèi)元素出棧時(shí)一定可以擴(kuò)展到數(shù)組的末尾
        // 特殊情況2：彈出棧頂后棧為空，一定可以擴(kuò)散到數(shù)組最左邊
        // 特殊情況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++) {
            // 當(dāng)前元素的高度嚴(yán)格小于棧頂元素的高度時(shí)，出棧
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                int height = heights[stack.removeLast()];
                // 特殊情況3：棧中存在高度相等的元素，出棧
                while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                    stack.removeLast();
                }
                // 特殊情況2：彈出棧頂后棧為空，一定可以擴(kuò)散到數(shù)組最左邊
                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：遍歷完成后，棧內(nèi)元素出棧時(shí)一定可以擴(kuò)展到數(shù)組的末尾
            int width = stack.isEmpty() ? len : (len - stack.peekLast() - 1);
            maxArea = Math.max(maxArea, width * height);
        }
        return maxArea;
    }
}

優(yōu)化法三：

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;
    }
}

?文章來源地址http://www.zghlxwxcb.cn/news/detail-775439.html

到了這里，關(guān)于LeetCode 84. 柱狀圖中最大的矩形的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！