當前位置:網站首頁>[LeetCode]劍指 Offer II 038. 直方圖最大矩形面積

[LeetCode]劍指 Offer II 038. 直方圖最大矩形面積

2022-01-28 13:17:03 普通男性人類

[LeetCode]劍指 Offer II 038. 直方圖最大矩形面積

題目

給定非負整數數組 heights ,數組中的數字用來錶示柱狀圖中各個柱子的高度。每個柱子彼此相鄰,且寬度為 1 。

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

示例

示例 1:

輸入:heights = [2,1,5,6,2,3]
輸出:10
解釋:最大的矩形為圖中紅色區域,面積為 10

示例 2:

輸入: heights = [2,4]
輸出: 4

方法

單調棧

class Solution {
    
    public int largestRectangleArea(int[] heights) {
    
       // 創建一個棧存放遞增的柱子
        Deque<Integer> stack = new LinkedList<>();
        // 壓入一個-1的下標,用來處理棧頂左側沒有柱子的情况
        stack.push(-1);
        // 記錄最大矩形面積
        int maxArea = 0;
        // 遍曆數組
        for (int i = 0; i < heights.length; i++) {
    
            // 若棧有柱子元素(-1是想象虛擬的柱子),並且棧頂元素大於當前遍曆的柱子高度執行邏輯
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
    
                // 彈出棧頂元素,計算棧頂元素的最大矩形面積
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(height * width, maxArea);
            }
            stack.push(i);
        }
        // 遍曆完數組後,棧可能還有柱子的執行邏輯
        while (stack.peek() != -1) {
    
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(height * width, maxArea);
        }
        return maxArea;
    }
}

1 先壓入-1, 錶示左側無柱體
2 i - stack.peek() - 1錶示 選中高度的柱體到它左右兩側更矮的柱體的距離,也就是寬度。

版權聲明
本文為[普通男性人類]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201281317024841.html

隨機推薦