LeetCode 84 詳解：Largest Rectangle in Histogram (柱狀圖中最大矩形)

題目描述

給定非負整數陣列 heights 表示柱狀圖各柱高度（寬度均為 1），找出能勻稱在柱狀圖內的最大矩形面積。

範例：heights = [2,1,5,6,2,3] → 最大面積 = 10（高度 5、寬度 2 的矩形，或高度 2、寬度 5 的矩形）。

核心洞察

最大矩形的高度必等於某根柱的高度。若固定高度為 heights[i]，最大寬度為向左右擴展至首個高度 < heights[i] 的柱。暴力枚舉每根柱向兩側擴展為 O(n²)。

單調棧優化：O(n) 解法

維護單調遞增棧存儲柱的索引。遍歷柱狀圖：

1. 若棧空或 heights[i] ≥ heights[stk.top()] → 入棧
2. 否則反覆彈出棧頂 tp，以 heights[tp] 為高計算面積：
   • 寬度 = i - stk.top() - 1（彈出後新棧頂為左側第一個更矮的柱）
   • 若棧空 → 寬度 = i（左邊無更矮柱）
3. 為觸發剩餘柱彈出，末尾追加高度 0 的哨兵柱
4. 棧底初始放入 -1 作為左邊界哨兵

Python 實作

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)          # 哨兵
        stack = [-1]               # 索引棧，-1 為左邊界
        max_area = 0
        
        for i, h in enumerate(heights):
            while h < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        
        heights.pop()              # 恢復原陣列（可選）
        return max_area

關鍵點圖解

以 [2,1,5,6,2,3] 為例：

複雜度分析

• 時間：O(n) — 每個索引最多入棧、出棧各一次
• 空間：O(n) — 棧最多存 n+1 個索引

常見變體與延伸

1. 矩陣中最大全 1 子矩陣：逐行累積高度，每行作為柱狀圖求解
2. 環形柱狀圖：複製陣列接在後面，限制寬度 ≤ n
3. 最大子矩陣和：前綴和 + 單調棧維護最小前綴和

總結

單調棧是解決「區間最值邊界」問題的利器。本題通過「以每根柱為高的最大矩形」轉化，利用棧維護左側第一個更矮柱，右側在遍歷中自然確定，實現 O(n) 最優解。掌握「哨兵技巧」（頭尾添加邊界值）能大幅簡化邊界條件判斷。