Monotonic-Stack

這篇在解決什麼

一整族題目長得完全不一樣——最大矩形、接雨水、等幾天會變暖、所有子陣列最小值的總和——但骨架是同一個：對每個元素，找出兩側第一個比它大／小的位置。暴力對每個元素往兩邊掃是 O(n²)，單調棧一趟 O(n) 解決。

難的不是資料結構（就是個棧），而是三件事：

1. 什麼時候該算——多數人的第一版會在每一步重掃整個棧，退化回 O(n²)
2. 比較用 > 還是 >=——重複值一處理錯就重複計算，而且小測資看不出來
3. 這題到底屬不屬於這個模式——判斷訊號長什麼樣

一、核心：彈出的那一刻，資訊才完備

棧裡放的是「還沒結案的元素」。一個元素進棧時，它的左界已知（見下）、右界未知，只能先掛帳。當某個新元素把它擠出去，那個新元素就是它的右界——這一刻左右都齊了，算一次，結案。

heights: [2, 1, 5, 6, 2, 3]
index:    0  1  2  3  4  5

i=4（值 2）進場，棧內 index [1, 2, 3]（高度 1 < 5 < 6）
  6 被擠出 → 右界就是 i=4，彈完露出的棧頂 2 是左界 → 寬 4-2-1 = 1
  5 被擠出 → 右界就是 i=4，彈完露出的棧頂 1 是左界 → 寬 4-1-1 = 2
  1 擋住   → 停止，i=4 入棧，它的左界就是現在的棧頂 1

二、模板：一趟掃描，左右界同時到手

// Time: O(n)   每個 index 恰好入棧一次、出棧至多一次
// Space: O(n)  最壞情況整個陣列都堆在棧裡
// left[i]  = 左邊第一個 a[j] <  a[i] 的 j，不存在為 -1
// right[i] = 右邊第一個 a[j] <= a[i] 的 j，不存在為 n
pair<vector<int>, vector<int>> smallerBounds(const vector<int>& a) {
  int n = a.size();
  vector<int> left(n, -1), right(n, n), st;  // st 存 index
  for (int i = 0; i < n; ++i) {
    while (!st.empty() && a[st.back()] >= a[i]) {
      right[st.back()] = i;  // i 把它擠出去，就是它的右界
      st.pop_back();
    }
    left[i] = st.empty() ? -1 : st.back();  // 彈完露出的棧頂就是左界
    st.push_back(i);
  }
  return {left, right};
}

注意 left 和 right 的嚴格性是不對稱的：左邊是 <，右邊是 <=。這不是筆誤，是必要的。

四個變體，旋鈕只有一個

要找「更大」還是「更小」，只差彈出條件的比較符號：

記法：彈出條件的比較符號反過來，就是棧內的單調方向（用 > 彈 → 棧遞增），而加不加等號決定嚴格性歸左邊還是右邊（等號在彈出條件裡 → 右界寬鬆、左界嚴格）。

不需要「由右往左掃」的變體：一趟由左往右就同時拿到左右兩界了。真的只要單邊時，省掉另一個陣列即可。

三、貢獻法：翻轉提問的方向

這是這族題目真正的思想。要求「所有子陣列的某個量的總和／最大值」，子陣列有 O(n²) 個，逐一枚舉必爆。貢獻法改問：

不問「每個子陣列的答案是多少」，改問「每個元素貢獻了多少子陣列」。

以「子陣列最小值總和」為例：元素 a[mid] 當最小值的子陣列，左端點可選 (left, mid] 共 mid - left 種、右端點可選 [mid, right) 共 right - mid 種，貢獻就是 (mid - left) * (right - mid) * a[mid]。n 個元素各算一次，O(n) 完成。

// Time: O(n)
// Space: O(n)
// LeetCode 0907：所有子陣列最小值的總和
class Solution {
 public:
  int sumSubarrayMins(vector<int>& arr) {
    const int MOD = 1e9 + 7;
    int n = arr.size();
    vector<int> st;
    long long ans = 0;
    for (int i = 0; i <= n; ++i) {  // i == n 當哨兵，逼出棧內殘留
      while (!st.empty() && (i == n || arr[st.back()] >= arr[i])) {
        int mid = st.back();
        st.pop_back();
        int l = st.empty() ? -1 : st.back();
        long long cnt = (long long)(mid - l) * (i - mid);  // 左端點數 × 右端點數
        ans = (ans + cnt % MOD * arr[mid]) % MOD;
      }
      st.push_back(i);
    }
    return ans;
  }
};

同一個骨架，換掉「彈出時算什麼」就是不同的題：

四、另一族：彈出不是結算，是丟棄

同樣是單調棧，0402-Remove-K-Digits、0316-Remove-Duplicate-Letters 這類構造字典序最優解的題，彈出時什麼都不算——彈出就是「這個字元不要了」。

// Time: O(n)
// Space: O(n)
// LeetCode 0402：從 num 刪掉 k 位，使剩下的數字最小
class Solution {
 public:
  string removeKdigits(string num, int k) {
    string st;
    for (char c : num) {
      while (!st.empty() && k > 0 && st.back() > c) {  // 前面較大的位數優先刪
        st.pop_back();
        --k;
      }
      st.push_back(c);
    }
    st.resize(st.size() - k);  // k 還有殘額（原字串非遞減），從尾巴砍
    int p = st.find_first_not_of('0');
    return p == string::npos ? "0" : st.substr(p);
  }
};

兩族的差別值得記牢：

五、共通陷阱

六、和鄰近工具的分界

Related Problems

0084-Largest-Rectangle-in-Histogram — 結算型的集大成，左右界都要
0739-Daily-Temperatures — 結算型最乾淨的原型，只要右界
0907-Sum-of-Subarray-Minimums — 貢獻法的標準題，也是嚴格性陷阱的教科書案例
0042-Trapping-Rain-Water — 遞減棧，逐層結算凹槽
0402-Remove-K-Digits — 構造型的原型
0853-Car-Fleet — 同款「新元素進場結算舊帳」，改成由右往左掃
0239-Sliding-Window-Maximum — 換成 deque 的近親，攤還論證完全相同