陳憲億 Joseph Chen | Software Engineer & AI Developer

Joseph Chen

2026

14 min read

3 題精講

EP.06 學了基礎 Stack，這篇進階：Monotonic Stack（單調棧）。

Monotonic Stack 的概念很簡單——在 push 新元素之前，先把 stack 裡所有「不符合單調條件的元素」pop 出來。這個 pop 的動作不是多餘的，每個被 pop 出來的元素，都正好找到了它的「下一個更大值」。

這個模式能把許多 O(n²) 的「找下一個更大/更小」問題，降到 O(n)。

Monotonic Stack 是什麼？

單調遞增棧（底大頂小）

Stack 從底到頂值遞減（頂端永遠是最小的）。 push 時，把所有比新元素大的 pop 掉。用來找「右邊第一個更大的元素」。

單調遞減棧（底小頂大）

Stack 從底到頂值遞增（頂端永遠是最大的）。 push 時，把所有比新元素小的 pop 掉。用來找「右邊第一個更小的元素」。

通用框架

monotonic_stack_template.py

stack = []   # 存 index（不存值，方便計算距離）

for i, val in enumerate(nums):
    # 維護單調性：把不符合條件的 pop 出來
    while stack and nums[stack[-1]] < val:   # 找「下一個更大值」
        idx = stack.pop()
        # nums[idx] 的「右邊第一個更大值」就是 val（在 index i）
        result[idx] = i - idx   # 或其他計算

    stack.append(i)

關鍵：stack 裡存的通常是 index（不是值），因為我們往往需要計算距離或對應回原陣列的值。

🌡️

Part 1 — Daily Temperatures

#739 · Medium · 幾天後會更暖？

題目

給一個每日氣溫陣列 temperatures，回傳一個陣列 answer，answer[i] 代表第 i 天之後幾天會迎來更高溫，若之後沒有更高溫則為 0。

temperatures = [73,74,75,71,69,72,76,73]

answer = [1, 1, 4, 2, 1, 1, 0, 0]

視覺化：棒狀圖 + stack 變化

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

i / temp動作stack（index）answer 更新

i=0, 73push 0[0]—

i=1, 74pop 0（74>73），push 1[1]ans[0]=1-0=1

i=2, 75pop 1（75>74），push 2[2]ans[1]=2-1=1

i=3, 71push 3[2,3]—

i=4, 69push 4[2,3,4]—

i=5, 72pop 4（72>69），pop 3（72>71），push 5[2,5]ans[4]=5-4=1, ans[3]=5-3=2

i=6, 76pop 5（76>72），pop 2（76>75），push 6[6]ans[5]=6-5=1, ans[2]=6-2=4

i=7, 73push 7[6,7]—

結束剩餘 stack: [6,7]—ans[6]=ans[7]=0

daily_temperatures.py

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []   # 存 index，單調遞減棧（棧頂是待找答案的最小溫度）

    for i, temp in enumerate(temperatures):
        # 當前溫度比棧頂高 → 棧頂找到了「下一個更高溫」
        while stack and temperatures[stack[-1]] < temp:
            idx = stack.pop()
            answer[idx] = i - idx   # 距離就是天數差

        stack.append(i)

    # stack 剩餘的 index 對應 answer 已預設為 0，不用處理
    return answer

⏱ Time: O(n)💾 Space: O(n)

為什麼是 O(n)？

每個 index 最多被 push 一次、pop 一次，所以 while 迴圈裡的所有 pop 操作加起來也是 O(n)。外層 for 迴圈 O(n)，總體 O(n)——這就是 Monotonic Stack 的威力。

🔭

Part 2 — Next Greater Element I

#496 · Easy · 找 nums2 中的下一個更大值

題目

nums1 是 nums2 的子集。對 nums1 中的每個元素，找出它在 nums2 中右邊第一個更大的元素，若不存在回傳 -1。

nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

4 的右邊沒有更大的 → -1；1 的右邊第一個更大的是 3；2 的右邊沒有更大的 → -1

思路：先預處理 nums2，再查表

這題的關鍵不是直接對 nums1 操作，而是先對 nums2 做一次 Monotonic Stack，建立一張「每個值 → 其下一個更大值」的 HashMap。然後對 nums1 的每個元素，直接查這張表就好。

nums2 = [1, 3, 4, 2] 的預處理

i / val動作next_greater 更新

i=0, 1push 1—

i=1, 3pop 1（3>1），push 3next_greater[1] = 3

i=2, 4pop 3（4>3），push 4next_greater[3] = 4

i=3, 2push 2（2<4）—

結束剩餘 [4, 2]next_greater[4]=next_greater[2]=-1

最終 HashMap：{1:3, 3:4, 4:-1, 2:-1}

next_greater_element.py

def nextGreaterElement(nums1: list[int], nums2: list[int]) -> list[int]:
    # Step 1：對 nums2 做 Monotonic Stack，建 HashMap
    next_greater = {}   # val → 右邊第一個更大值
    stack = []          # 單調遞減棧（存值）

    for val in nums2:
        while stack and stack[-1] < val:
            next_greater[stack.pop()] = val
        stack.append(val)

    # stack 剩餘的元素，右邊沒有更大值
    for val in stack:
        next_greater[val] = -1

    # Step 2：查表
    return [next_greater[x] for x in nums1]

⏱ Time: O(n + m)💾 Space: O(n)

和 #739 的差異

#739 存的是 index（因為需要計算距離 i - idx）； #496 存的是 值本身（只需要查「這個值對應的下一個更大值」，不需要位置資訊）。根據需求決定 stack 存 index 還是值，是 Monotonic Stack 最常見的判斷點。

🌧️

Part 3 — Trapping Rain Water

#42 · Hard · 接了多少雨水？

題目

給一個表示地形高度的陣列，計算下雨後整個地形能接住多少單位的雨水。

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

Output: 6

高度示意（height = [0,1,0,2,1,0,1,3,1,0,1,2]）

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

橘色：左右最高牆；藍色：最高柱。中間低窪處可接水

解法一：Two Pointers（推薦記這個）

每個位置能接的水量 = min(左邊最高, 右邊最高) - 自身高度。用左右兩個指針，從低的那側往中間走，始終能保證當前那側的「最高牆」是確定的。

Two Pointers 直覺

• left 指向左端，right 指向右端，left_max 和 right_max 追蹤各側見過的最大值

• 若 height[left] < height[right]：左側牆較矮，左側積水量由 left_max 決定

→ 積水 = left_max - height[left]，left 右移

• 反之，處理右側，right 左移

trapping_rain_water_two_pointers.py

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]     # 更新左側最高牆
            else:
                water += left_max - height[left]   # 積水！
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]   # 更新右側最高牆
            else:
                water += right_max - height[right]  # 積水！
            right -= 1

    return water

⏱ Time: O(n)💾 Space: O(1)

解法二：Monotonic Stack

用單調遞減棧，當遇到比棧頂更高的柱子時，就可以計算「兩個較高柱子夾著中間凹陷」能接的水量。這是橫向計算積水（一層一層算），Two Pointers 是縱向（一列一列算）。兩種思路都正確。

trapping_rain_water_stack.py

def trap(height: list[int]) -> int:
    stack = []   # 單調遞減棧，存 index
    water = 0

    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            mid = stack.pop()               # 凹槽的底部

            if not stack:
                break                       # 左邊沒有牆，積不了水

            left = stack[-1]                # 左牆
            width = i - left - 1            # 凹槽寬度
            bounded_height = min(height[left], h) - height[mid]  # 可積水高度
            water += width * bounded_height

        stack.append(i)

    return water

⏱ Time: O(n)💾 Space: O(n)

Two Pointers

✅ O(1) 空間，更優
✅ 程式碼更短，更直觀
✅ 面試首選解法

Monotonic Stack

✅ 思維框架和其他題一致
✅ 橫向計算，適合變形題
❕ O(n) 空間

三題統一對比

題目	Stack 存什麼	pop 時做什麼	複雜度
#739 Daily Temperatures	index	`ans[idx] = i - idx`	O(n) / O(n)
#496 Next Greater Element	值	`map[val] = cur_val`	O(n+m) / O(n)
#42 Trapping Rain Water	index	計算左牆右牆夾住的積水面積	O(n) / O(n)

識別 Monotonic Stack 題目的訊號

→「找右邊（或左邊）第一個更大/更小的元素」
→「計算每個元素作為最大/最小值時能影響的範圍」
→暴力解是兩層 for loop O(n²)，但感覺「每個元素只會被處理一次」
→stack 裡的元素一直在「等待」找到自己的答案（被 pop 時就是找到答案的時刻）

這篇學到什麼

📚Monotonic Stack 的核心：push 前把不符合單調性的元素 pop 出來，被 pop 的元素「此刻就找到了答案」

🌡️#739 Daily Temperatures：Stack 存 index，pop 時 ans[idx] = i - idx，O(n) 解決 O(n²) 問題

🔭#496 Next Greater Element：先對 nums2 建 HashMap，再對 nums1 查表；Stack 存值（不用知道位置）

🌧️#42 Trapping Rain Water：Two Pointers 是首選（O(1) 空間）；Monotonic Stack 解法思維更統一

💡Stack 存 index 還是值？需要計算距離或回查陣列 → 存 index；只需記錄「這個值的答案」→ 存值

EP.17 — Intervals

Merge、Non-overlapping、Meeting Rooms II

EP.19 — Trie

Implement Trie、Add and Search

LeetCode

Monotonic Stack

Daily Temperatures

Next Greater

Trapping Rain Water

Python

EP.18

EP.18 — Monotonic Stack：維持單調的 Stack