LeetCode 刷題日記
EP.06

Stack
後進先出，解決「配對」問題

#20 Valid Parentheses — Stack 最經典的應用，也是單調棧的入口

Joseph Chen
October 2024
Back to Blog
5 min read
1.2k views

Stack（堆疊）是「後進先出（LIFO）」的資料結構。感覺很抽象，但只要理解一個使用場景，就會豁然開朗：當你需要記住「最近遇到的東西」，等未來某個時機來配對它，這就是 Stack 的時機。Valid Parentheses 是最經典的例子。

題目

給一個只包含 ( ) [ ] { } 的字串，判斷括號是否合法配對。

Input / Output
"[]"       → True
"([{}])"   → True
"[({)"     → False  (順序不對)
"["        → False  (沒有閉合)

Stack 是什麼？

Stack 就像一疊盤子——你只能從最上面放（push）和取（pop）。

push 'a'

a
bottom

push 'b'

a
b
bottom

push 'c'

a
b
c
bottom

pop → 'c'

a
b
bottom
Python 用 list 模擬 Stack
stack = []

stack.append('a')   # push → ['a']
stack.append('b')   # push → ['a', 'b']
stack.append('c')   # push → ['a', 'b', 'c']

top = stack.pop()   # pop → 'c'，stack = ['a', 'b']
top = stack[-1]     # peek（只看頂端，不取出）→ 'b'

len(stack) == 0     # 判斷 stack 是否為空

解題關鍵：用 dict 建立閉括號的映射

遇到開括號（( [ {）就 push 進去；遇到閉括號（) ] }）就和 stack 頂端比對，是不是它對應的開括號。

用一個 dict 存「閉括號 → 對應開括號」的映射，讓比對邏輯變得非常乾淨：

映射關係
Map = {
    ')': '(',
    '}': '{',
    ']': '['
}

# 遇到 ')' → 查 Map[')'] = '(' → stack 頂端必須是 '('

完整解法

Valid Parentheses — 你的解法
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        Map = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        for char in s:
            if char not in Map:
                # 開括號 → push 進 stack
                stack.append(char)
                continue

            # 閉括號 → 比對 stack 頂端
            if not stack or Map[char] != stack.pop():
                return False

        return not stack   # stack 為空代表全部配對完成
⏱ Time: O(n)💾 Space: O(n)
char not in Map閉括號才在 Map 裡，所以這個判斷是「遇到開括號」→ push
not stackstack 是空的，沒有東西可以配對，直接回傳 False（例如輸入 ")"）
stack.pop()取出 stack 頂端並同時移除，直接和 Map[char] 比較
return not stackstack 為空代表所有開括號都有對應的閉括號，合法

逐步追蹤 "([{])"

char動作stack
(開括號 → push['(']
[開括號 → push['(', '[']
{開括號 → push['(', '[', '{']
}閉括號 → Map['}']='{'，pop='{' ✅['(', '[']
]閉括號 → Map[']']='['，pop='[' ✅['(']
)閉括號 → Map[')']='('，pop='(' ✅[]
stack 為空 → return True ✅

Stack 的進階：單調棧（Monotonic Stack）

Valid Parentheses 是 Stack 的入門題。進階版是「單調棧」——維護一個單調遞增或遞減的 stack，用來解決「找下一個更大/更小的元素」這類問題。

Daily Temperatures（日均溫）

給一個溫度陣列，對每天求「幾天後會遇到更高的溫度」。用單調遞減棧：把下標存進去，遇到更高溫度時，stack 裡排在前面的天都找到了答案。

單調棧模板 — Daily Temperatures
def dailyTemperatures(temps):
    stack = []      # 存 index，維護單調遞減
    result = [0] * len(temps)

    for i, temp in enumerate(temps):
        # 當前溫度比 stack 頂端高 → 頂端找到答案了
        while stack and temps[stack[-1]] < temp:
            idx = stack.pop()
            result[idx] = i - idx   # 等了幾天
        stack.append(i)

    return result

Stack 適合的場景有個共同特徵：「現在遇到的東西，需要等未來某個條件成立才能處理」。Valid Parentheses 是等閉括號，單調棧是等更大/更小的元素。認出這個模式，就認出了 Stack。

本篇重點整理

📚Stack = 後進先出，Python 用 list.append() / list.pop() 實作
🗺️用 dict 建閉括號映射，讓配對邏輯變成一行：Map[char] != stack.pop()
✅最後 return not stack：空 stack 表示全部配對完成
🔥單調棧：解決「找下一個更大/更小元素」的問題，進階必學

上一篇

EP.05 — Sliding Window

Best Time to Buy and Sell Stock

下一篇

EP.07 — Binary Search

即將推出

LeetCode
Stack
String
Python
EP.06