[algorithms] Monotone Stack 單調棧

視覺化概覽

stateDiagram-v2
    state "i=0: push 2\n棧: [2]" as S0
    state "i=1: 1<2, push\n棧: [2, 1]" as S1
    state "i=2: 2>1, pop 1→result[1]=2\n棧: [2, 2]" as S2
    state "i=3: 4>2, pop→result[2]=4\n4>2, pop→result[0]=4\n棧: [4]" as S3
    state "i=4: 3<4, push\n棧: [4, 3]" as S4
    state "結果: [4, 2, 4, -1, -1]" as SR

    [*] --> S0 : nums=[2,1,2,4,3]
    S0 --> S1
    S1 --> S2
    S2 --> S3
    S3 --> S4
    S4 --> SR

什麼是單調棧？

單調棧是一種棧內元素保持單調遞增或遞減的特殊棧。用於高效地找到每個元素的「下一個更大/更小的元素」。

單調遞增棧（棧底到棧頂遞增）：
底 [1, 3, 5, 7] 頂    ← 新元素 > 棧頂才入棧

單調遞減棧（棧底到棧頂遞減）：
底 [7, 5, 3, 1] 頂    ← 新元素 < 棧頂才入棧

模板

下一個更大元素

int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // 存索引
 
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i]; // 找到了下一個更大的
        }
        stack.push(i);
    }
    return result;
}

執行過程

nums = [2, 1, 2, 4, 3]

i=0: stack=[0(2)]
i=1: 1<2, push → stack=[0(2), 1(1)]
i=2: 2>1, pop 1→result[1]=2; 2==2 不pop; push → stack=[0(2), 2(2)]
i=3: 4>2, pop 2→result[2]=4; 4>2, pop 0→result[0]=4; push → stack=[3(4)]
i=4: 3<4, push → stack=[3(4), 4(3)]

result = [4, 2, 4, -1, -1]

四種變體

目標	棧的單調性	遍歷方向
下一個更大	遞減棧	左→右
下一個更小	遞增棧	左→右
上一個更大	遞減棧	左→右
上一個更小	遞增棧	左→右

經典應用

每日溫度

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
result       = [1,  1,  4,  2,  1,  1,  0,  0]

73 等 1 天 → 74
75 等 4 天 → 76

柱狀圖中最大矩形

heights = [2, 1, 5, 6, 2, 3]

    ██
   ████
   ████
   ████ ██
██ ████ ████
████████████
2  1  5  6  2  3

最大矩形面積 = 10（高度 5，寬度 2）

接雨水

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

            ██
      ██≈≈≈≈████≈≈██
   ██≈≈██≈≈████████████
   ████████████████████
0  1  0  2  1  0  1  3  2  1  2  1

接水量 = 6

時間複雜度

所有元素最多入棧一次、出棧一次：O(n)

經典題目

1. 下一個更大元素 I - LeetCode 496
2. 下一個更大元素 II（環形） - LeetCode 503
3. 每日溫度 - LeetCode 739
4. 柱狀圖最大矩形 - LeetCode 84
5. 接雨水 - LeetCode 42
6. 最大矩形 - LeetCode 85
7. 股票價格跨度 - LeetCode 901

相關檔案

• Java 實作：MonotoneStack.java