Stack¶

Monotonic stack¶

以「當前元素」為對象 (常見於 Next Greater Element)¶

這種模式比較直觀。當我們遍歷到 \(x\) 時，我們是為了幫 \(x\) 找答案。

• 思維： 「我要幫現在手上的這個數字找它右邊第一個比它大的數。」

• 動作： 如果 \(x\) 比棧頂大，那 \(x\) 就是棧頂的答案，棧頂出棧。

以「堆頂元素」為對象¶

這種模式通常用於需要同時知道左右邊界的場景，例如 「以 \(h\) 為高度的最大矩形」。

• 思維： 「當前元素 \(x\) 破壞了單調性，這意味著堆頂元素 (\(top\)) 的右邊界確定了。」

• 核心邏輯：

  • 堆頂 (\(top\)) 是我們當前要計算的「對象」。
  • 當前元素 (\(i\)) 是 \(top\) 的右邊界（第一個比它小的數）。
  • 堆頂下方的元素 (\(top-1\)) 是 \(top\) 的左邊界（另一個第一個比它小的數）。