解題說明
Largest Rectangle in Histogram
題目描述：
給定一個整數陣列 heights，代表柱狀圖中每根柱子的高度，每根柱子的寬度均為 1。找出能在柱狀圖中形成的最大矩形面積。矩形的高度受限於範圍內最矮的柱子。
解題思路： 對每根柱子而言，以它的高度為矩形高度時，矩形能延伸的最大寬度取決於：向左找到第一根比它矮的柱子、向右找到第一根比它矮的柱子。單調遞增棧正好能高效地解決這個問題。
單調遞增棧解法：
維護一個棧，存放索引，且對應的高度從底部到頂部保持嚴格遞增。
遍歷每個柱子（加上末尾的哨兵高度 0）：
- 當遇到高度比棧頂更矮的柱子時，彈出棧頂（設其高度為
h、索引為top）。 - 計算以
h為高的矩形寬度：- 左邊界：彈出後新的棧頂索引（若棧為空則為 -1）。
- 右邊界：當前正在處理的索引
i。 - 寬度 =
i - (new_stack_top) - 1。
- 更新最大面積
max_area = max(max_area, h * width)。 - 繼續彈出直到棧為空或棧頂高度不大於當前高度，再將當前索引壓入棧。
在陣列末尾補一個高度 0（或在迴圈後處理剩餘棧中元素），可以確保所有柱子都被正確處理。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個索引最多被壓入棧一次、彈出棧一次，因此所有的壓棧與彈棧操作總計為 2n 次，整體為線性時間。
空間複雜度：O(n) — 最壞情況下（高度嚴格遞增），所有索引都會同時存在於棧中，棧的大小為 O(n)。
虛擬碼
1. Append 0 to heights as a sentinel (forces all remaining bars to be processed).
2. Initialize an empty stack st and max_area = 0.
3. For each index i from 0 to len(heights) - 1:
a. While st is not empty and heights[st.top()] > heights[i]:
- Pop top index, record its height h.
- left_boundary = st.top() if st not empty, else -1.
- width = i - left_boundary - 1.
- max_area = max(max_area, h * width).
b. Push i onto the stack.
4. Return max_area.其他解法
暴力法 O(n²)：對每對 (left, right)，找其間最小高度並計算面積。或對每根柱子，向左右擴展找第一根更矮的柱子。實作簡單但效率低。
預計算左右邊界陣列 O(n) 時間 O(n) 空間：先用單調棧求出每根柱子的「左側第一個更矮柱子的索引」（left_bound）和「右側第一個更矮柱子的索引」（right_bound），再統一計算 heights[i] * (right_bound[i] - left_bound[i] - 1) 的最大值。這是單次遍歷解法的等價分拆版本，程式碼結構更清晰，但需要額外的兩個 O(n) 陣列。兩種方式時間與空間複雜度相同。
延伸思考
- 本題是 LeetCode 85（Maximal Rectangle）的核心子問題。若輸入變為一個由 '0' 和 '1' 組成的二維矩陣，你會如何對每一列應用本題解法來求最大全 '1' 矩形？
- 本題的單調棧是「遞增棧」（遇到更小元素時觸發計算），而 Sliding Window Maximum 使用「遞減佇列」。請比較這兩種單調資料結構的共同點與適用場景。
- 在計算寬度時，公式為
i - left_boundary - 1，其中left_boundary是彈出後棧頂的索引（或 -1）。請以一個具體例子說明為什麼這個公式能正確計算出矩形的最大可延伸寬度。