LeetCode 刷題日記
EP.16

EP.16 — Greedy：
每一步都選當下最好的

#55 Jump Game · #45 Jump Game II · #134 Gas Station
— 貪心演算法不是亂猜，是有數學保證的局部最優

Joseph Chen

2026
12 min read
3 題精講

Backtracking 是「列出所有可能再找答案」，Greedy（貪心）則是反過來：每一步都直接選當下看起來最好的選擇，不回頭，不窮舉。

這聽起來很冒險——局部最優真的能推到全局最優嗎？多數情況下不行， 但 Greedy 題目的設計保證了這件事成立。難點不是寫程式，而是想出「貪什麼」這個關鍵直覺。

這篇用三道 Jump Game 家族 + Gas Station 把 Greedy 的核心思維打通。

Greedy 的思維方式

🔍

找「貪心選擇」

在每個決策點，找一個局部最優的選擇，而且這個選擇不會讓全局答案變差。

🚫

不回頭

選了就選了，不像 DP 維護所有可能狀態，不像 Backtracking 撤銷再試。

✅

用反證法驗證

如果選了最大的 X，假設選更小的 Y 能更好，會矛盾嗎？若矛盾，貪心就是對的。

Greedy vs DP：什麼時候用哪個？

• Greedy：局部最優 = 全局最優（有數學保證），O(n) 或 O(n log n)

• DP：局部最優不保證全局最優，需要維護所有子問題的解，O(n²) 或更高

• 判斷方法：試著用反證法推，如果能證明 Greedy 選擇不會讓答案更差，就用 Greedy

🐸

Part 1 — Jump Game

#55 · Medium · 能不能跳到終點？

題目

給一個非負整數陣列 nums， 你站在第 0 格，nums[i]代表你在第 i 格最多可以往右跳幾步。判斷能否到達最後一格。

nums = [2,3,1,1,4] → True（0→1→4 或 0→2→3→4）

nums = [3,2,1,0,4] → False（第 3 格必定卡住）

Greedy 直覺：維護「最遠能到哪」

不需要模擬每一種跳法，只需要在走過的每一格，更新「到目前為止能到達的最遠位置」。 如果走到某格時，這格的 index 已經超過最遠位置，代表走不到這裡，回傳 False。

nums = [2, 3, 1, 1, 4] 的過程

0

i=0, nums[0]=2 → max_reach = max(0, 0+2) = 2

max=2
1

i=1, nums[1]=3 → max_reach = max(2, 1+3) = 4

max=4
2

i=2, nums[2]=1 → max_reach = max(4, 2+1) = 4

max=4
3

i=3, nums[3]=1 → max_reach = max(4, 3+1) = 4

max=4
4

i=4 ≤ max_reach=4 → 到達終點 ✅

max=4

卡住的情況（nums = [3,2,1,0,4]）：

3
[0]
2
[1]
1
[2]
0
[3]
4
[4]

i=3 時 max_reach 只有 3，但從 index 3（值為 0）出發跳不到更遠， 後面 i=4 時 4 > max_reach → False

jump_game.py
def canJump(nums: list[int]) -> bool:
    max_reach = 0   # 目前能到達的最遠 index

    for i in range(len(nums)):
        if i > max_reach:       # 這格根本到不了
            return False
        max_reach = max(max_reach, i + nums[i])

    return True  # 走完所有可達格都沒卡住
⏱ Time: O(n)💾 Space: O(1)

貪心保證：為什麼維護 max_reach 就夠了？

因為我們不在意「怎麼到達」某一格，只在意「能不能到達」。 只要某格在 max_reach 範圍內，就一定能到（可以從前面某個格跳過來）。 所以追蹤「最遠能到哪裡」就完整地表達了所有可能的跳法。

🚀

Part 2 — Jump Game II

#45 · Medium · 最少幾跳能到終點？

題目

同樣的陣列設定，但這次保證一定能到達終點，問最少需要幾跳。

nums = [2,3,1,1,4] → 2（0→1→4，跳 2 次）

nums = [2,3,0,1,4] → 2（0→1→4）

思路：把每一跳視為一個「層」（BFS 概念）

這題的 Greedy 直覺很像 BFS 的層級：在當前這一跳能覆蓋的範圍裡，找到下一跳能到達的最遠位置。走到當前跳的邊界時，就必須跳一次，邊界更新為「下一跳能到的最遠」。

nums = [2, 3, 1, 1, 4]，模擬過程

初始
jumps=0cur_end=0far=0

站在 index 0，0 跳，當前覆蓋邊界 = 0

走 i=0
jumps=1cur_end=2far=2

i=0，far = max(0, 0+2) = 2。i 到達 cur_end(0)，跳一次，cur_end → far = 2

走 i=1,2
jumps=1cur_end=2far=4

i=1，far = max(2, 1+3) = 4。i=2，far = max(4, 2+1) = 4。

i=2 到邊界
jumps=2cur_end=4far=4

i(2) == cur_end(2)，再跳一次，cur_end → 4。已覆蓋終點 → 答案 = 2

jump_game_ii.py
def jump(nums: list[int]) -> int:
    jumps = 0
    cur_end = 0   # 當前這一跳覆蓋的最遠邊界
    far = 0       # 在當前跳範圍內，下一跳能到的最遠位置

    for i in range(len(nums) - 1):   # 不需要走到最後一格
        far = max(far, i + nums[i])

        if i == cur_end:   # 走到邊界了，必須跳一次
            jumps += 1
            cur_end = far  # 邊界更新為下一跳能到的最遠

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

為什麼不走最後一格？

range(len(nums) - 1)： 到達倒數第二格後如果 cur_end 已經 ≥ 最後一格，就不用再跳了。 多走一格會多算一跳。

和 #55 的差異

#55 只問「能不能到」，只需要 max_reach。 #45 問「最少幾跳」，需要額外追蹤「當前跳的邊界」來計算跳躍次數。

⛽

Part 3 — Gas Station

#134 · Medium · 從哪個加油站出發能繞一圈？

題目

n 個加油站排成一圈，gas[i] 是第 i 站的油量，cost[i] 是從第 i 站到第 i+1 站的耗油。 找出能繞完整圈的起始站 index，若不存在回傳 -1。答案唯一。

gas = [1,2,3,4,5]

cost = [3,4,5,1,2]

→ 3（從 index 3 出發可繞一圈）

兩個關鍵觀察

觀察一：全局可行性判斷

如果 sum(gas) < sum(cost)， 無論從哪裡出發都走不完，直接回傳 -1。

反過來，只要 sum(gas) ≥ sum(cost)，答案一定存在且唯一。這是這題最重要的數學保證。

觀察二：局部失敗 → 重設起點

從某個起點 start 出發，邊走邊累積油量差（tank += gas[i] - cost[i]）。 如果某一步 tank < 0，代表從 start 到 i 之間任何一個起點都無法到達 i+1。直接把 start 設為 i+1，重新開始。

為什麼可以跳過 start 到 i 之間的所有點？ 因為如果從 start 出發到 i 都是虧的（tank < 0），那從 start 和 i 之間任何一個中間點出發， 到 i 的時候油量只會更少（少了前段的正貢獻）。

gas=[1,2,3,4,5], cost=[3,4,5,1,2] 模擬

igas[i]cost[i]difftank動作
013-2-2tank<0，start→1，tank=0
124-2-2tank<0，start→2，tank=0
235-2-2tank<0，start→3，tank=0
34133ok
45236ok，走完 → 回傳 start=3
gas_station.py
def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    # 全局判斷：油不夠就直接不可能
    if sum(gas) < sum(cost):
        return -1

    tank = 0
    start = 0

    for i in range(len(gas)):
        tank += gas[i] - cost[i]

        if tank < 0:       # 從 start 無法到達 i+1
            start = i + 1  # 重設起點
            tank = 0       # 重設油量

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

為什麼最後的 start 一定是正確答案？

因為我們已知 sum(gas) ≥ sum(cost)，答案存在。 演算法從前往後找，每次 tank < 0 就把 start 往後移， 最終剩下的 start 是「沒有被淘汰的最後一個候選起點」。 而我們已經證明答案存在，所以這個候選點就是答案。

三題統一對比

題目貪什麼維護的變數複雜度
#55 Jump Game每格都更新最遠可達位置max_reachO(n) / O(1)
#45 Jump Game II在當前跳範圍內，最大化下一跳邊界jumps, cur_end, farO(n) / O(1)
#134 Gas Stationtank 變負時直接跳過所有可能的劣解起點tank, startO(n) / O(1)

識別 Greedy 題目的訊號

  • →問最大值、最小值、最少次數、能否達成（而非所有可能）
  • →每一步的選擇不影響之前已確定的選擇（無後效性）
  • →直覺上「每次選最好的」能讓整體也最好
  • →暴力解是 O(n²) 或更高，但感覺一次掃描就夠了

這篇學到什麼

🧠Greedy 難點在「貪什麼」，不是程式本身。要能用反證法說服自己局部最優 = 全局最優
🐸#55 Jump Game：維護 max_reach，走到超出 max_reach 的格子就回傳 False
🚀#45 Jump Game II：BFS 層的概念，走到 cur_end 邊界才跳一次，跳到 far 更新邊界
⛽#134 Gas Station：sum(gas) < sum(cost) 直接 -1；tank < 0 就把 start 重設為 i+1
⚡三題都是 O(n) 時間、O(1) 空間，這是 Greedy 相較 DP 最大的優勢

上一篇

EP.15 — Backtracking

Subsets、Permutations、Combination Sum

下一篇

EP.17 — Intervals

Merge Intervals、Non-overlapping

LeetCode
Greedy
Jump Game
Gas Station
Python
EP.16