LeetCode Largest Rectangle in Histogram：直方圖最大矩形

題目描述

給定 n 個非負整數代表直方圖柱高（寬度皆為 1），求最大矩形面積。

height = [2,1,5,6,2,3] 最大面積 = 10（高 5、寬 2）。

單調棧 O(N) 解法

核心思想：維護單調遞增棧（存索引）。遍歷柱子：

1. 棧空或當前高 ≥ 棧頂高 → 入棧。
2. 否則棧頂高 > 當前高 → 彈出棧頂 tp，以 height[tp] 為高計算面積：寬度 = i - stack.top() - 1（若棧空則寬度 = i）。更新最大值。重複直到可入棧。

為觸發剩餘棧元素計算，尾部添加高度 0 的哨兵。

C++ 實現

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        if (height.empty()) return 0;
        height.push_back(0); // 哨兵
        stack<int> st;
        int maxArea = 0;
        for (int i = 0; i < height.size(); ++i) {
            if (st.empty() || height[st.top()] < height[i]) st.push(i);
            else {
                int tp = st.top(); st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, height[tp] * width);
                --i; // 重新檢查當前 i
            }
        }
        return maxArea;
    }
};

波峰圖視角

將直方圖視為一組組「波峰圖」（遞增後驟降）。每次彈出序列即為一個波峰，可一次性計算該波峰所有可能矩形面積。單調棧正是高效分解波峰的工具。

複雜度

• 時間：O(N)，每索引進出棧各一次。
• 空間：O(N) 棧。