LeetCode 84：柱狀圖中最大矩形面積——單調棧優化解法

題目描述

給定 n 個非負整數表示柱狀圖各柱高度（寬度均為 1），求最大矩形面積。

示例

heights = [2,1,5,6,2,3]
最大面積 = 10（高度 5 和 6 形成寬度 2 的矩形）

解法一：暴力剪枝 O(n²)

枚舉右邊界，維護向左的最小高度，利用單調性剪枝跳過遞增段。雖然通過但非最優。

解法二：單調遞增棧 O(n) —— 推薦

核心思想

維護一個存儲索引的單調遞增棧。遍歷每個柱子：

• 若棧為空或當前高度 ≥ 棧頂高度 → 入棧
• 否則：反覆彈出棧頂 tp，以 heights[tp] 為高計算面積：
  • 寬度 = 棧空 ? 當前索引 i : i - st.top() - 1
  • 更新最大面積
• 遍歷結束後清空棧繼續計算

關鍵圖解

彈出時，棧內新頂元素是左側第一個比 heights[tp] 矮的柱子，當前 i 是右側第一個矮的，中間全 ≥ heights[tp]。

AC 代碼（C++）

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int maxArea = 0, n = heights.size();
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()]; st.pop();
                int w = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            st.push(i);
        }
        while (!st.empty()) {
            int h = heights[st.top()]; st.pop();
            int w = st.empty() ? n : n - st.top() - 1;
            maxArea = max(maxArea, h * w);
        }
        return maxArea;
    }
};

擴展應用

此題是 LeetCode 85：最大矩形（二維矩陣中全 1 子矩陣）的核心子程序，將每行作為柱狀圖底部累積高度即可套用。

複雜度

• 時間：O(n) —— 每個索引進棧出棧各一次
• 空間：O(n) —— 棧空間