📘 題目敘述
給你一個整數陣列 heights，表示直方圖中每個柱子的高度，其中每個柱子的寬度都是 1。
請回傳這個直方圖中，最大矩形的面積。
條件限制
1 <= heights.length <= 10^50 <= heights[i] <= 10^4
🧠 解題思路
這題的重點是：
如果我固定某一根柱子當作矩形的高度，那我就要知道它能往左延伸到哪裡、往右延伸到哪裡，直到遇到比它矮的柱子為止。
所以我會用單調 stack 來維護：
- 還沒有找到右邊第一個更矮柱子的 index
當我掃到一個比較矮的新柱子時，就代表 stack 裡某些比較高的柱子，它們的右邊界已經確定了。這時就可以把那些柱子拿出來算面積。
這份做法的核心就是：
- 每一根柱子在被 pop 出 stack 的那一刻
- 它的高度固定
- 它左邊第一個更矮的位置也知道
- 它右邊第一個更矮的位置也知道
所以就能直接算出以它為高度的最大矩形面積。
所有變數
s：單調 stack，存柱子的 indexans：目前找到的最大矩形面積n：陣列長度now：剛從 stack pop 出來、要拿來算面積的柱子 indexleft：now左邊第一個比它矮的柱子 index
🪜 主要流程步驟
1. 先在最後補一個高度 0
heights.push_back(0);
這一步很重要。
因為有些柱子一路到最後都沒有遇到右邊更矮的柱子，如果不補一個 0，它們就不會被 pop 出來，也就不會被計算到面積。
所以我在最後補一根高度為 0 的柱子，強迫 stack 裡剩下的柱子全部結算。
2. 用 stack 維護遞增高度的柱子 index
stack<int> s;
這個 stack 裡放的是 index，不是高度本身。
因為之後我要同時知道：
- 這根柱子的高度
heights[index] - 它的位置
- 它左右能延伸到哪裡
所以存 index 會比較方便。
而 stack 維持的性質是：
- 從底到頂對應的高度是單調不下降的
3. 從左到右掃每一根柱子
for (int i = 0; i < n; i++) {
我會依序看每個位置 i。
如果目前這根柱子比 stack 頂端還矮，就代表 stack 頂端那根柱子的右邊界出現了，該結算面積了。
4. 當目前柱子比較矮時，不斷 pop 並計算面積
while (!s.empty() && heights[s.top()] > heights[i]) {
int now = s.top();
s.pop();
這裡的意思是：
如果目前高度 heights[i] 比 stack 頂端那根柱子還矮，那麼 stack 頂端這根柱子就不能再往右延伸到 i 了。
所以：
i就是它右邊第一個更矮柱子的位置- 這時可以把它拿出來算面積
now 就是那根被拿出來結算的柱子 index。
5. 找出 now 左邊第一個更矮的位置
當 now 被 pop 掉之後，stack 新的頂端就是它左邊第一個比它矮的柱子。
如果 stack 已經空了，表示左邊根本沒有比它更矮的柱子，那我就把左邊界設成 -1。
所以這裡的 left 表示：
now左邊第一個更矮柱子的 index
而右邊第一個更矮柱子的 index 則是目前的 i。
6. 用高度 × 寬度算出以 now 為高的最大矩形
ans = max(ans, (i - left - 1) * heights[now]);
這一行是整題最核心的公式。
對柱子 now 來說：
- 高度就是
heights[now] - 左邊第一個更矮的位置是
left - 右邊第一個更矮的位置是
i
所以它真正能延伸的寬度就是：
i - left - 1
因此面積就是：
heights[now] * (i - left - 1)
每次算完就更新最大值 ans。
7. 把目前柱子 push 進 stack
s.push(i);
當前面所有比目前柱子高的都結算完之後，就把目前這根柱子放進 stack。
表示它現在還沒找到右邊第一個更矮柱子，之後再等未來的柱子來幫它決定右邊界。
8. 最後回傳答案
return ans;
因為最後補了一個 0，所以所有柱子都一定會被正確結算到。整個迴圈結束後，ans 就是最大矩形面積。
⏱️ 複雜度
設 n = heights.length（原本長度，不含最後補的那個 0）。
- 時間複雜度：
O(n)
每個 index 最多只會被 push 進 stack 一次、pop 出來一次。 - 空間複雜度：
O(n)
stack 最壞情況下可能存下所有柱子的 index。
💻 程式碼實作
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
int ans = 0;
heights.push_back(0);
int n = heights.size();
for (int i = 0; i < n; i++) {
while (!s.empty() && heights[s.top()] > heights[i]) {
int now = s.top();
s.pop();
int left;
if (s.empty()) {
left = -1;
} else {
left = s.top();
}
ans = max(ans, (i - left - 1) * heights[now]);
}
s.push(i);
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/largest-rectangle-in-histogram/