---
title: "Greedy 模板"
url: "https://laigary.com/interview/coding/greedy-template"
type: "note"
section: "coding"
date: "2026-07-27"
updated: "2026-07-27"
tags: ["Greedy"]
---

# Greedy 模板

Greedy 沒有一段可以照抄的 code。它是一個**判斷**：這一題能不能省掉搜尋，每一步直接選一個答案就往下走。

## 貪在哪裡

同一個問題，DP 和 Greedy 的差別不在答案，在**決定的時機**：

- **DP** — 每一步把所有分支展開，用記憶化避免重算，最後才知道哪條路最好
- **Greedy** — 證明每一步只有一個分支值得走，所以連展開都不用

所以 Greedy 可以看成 DP 的退化情形：決策樹每層只剩一個分支。「貪」指的是**當下就把最好的拿走，而且不回頭**。

## 為什麼一定要證明

局部最優不等於全域最優。最乾淨的反例是找零錢：

```text
coins = [1, 3, 4], amount = 6

貪心：拿 4 → 剩 2 → 拿 1 → 拿 1    共 3 枚
最佳：3 + 3                       共 2 枚
```

貪心在第一步就把 4 拿走，而 4 這個選擇讓剩下的 2 只能用兩個 1 湊。這就是為什麼 [322. Coin Change](/interview/coding/322-coin-change) 是 DP 不是 Greedy。

**「拿最大的」本身沒有任何保證。** 一題能不能貪，跟你多想拿到最大值無關，跟問題的結構有關。

## 交換論證

要證明能貪，用的幾乎都是同一招：

**假設有一個最佳解沒有採用我這一步的選擇。把它換成我的選擇，證明答案不會變差。既然不會變差，那「包含我的選擇」的最佳解一定存在。**

實際上會長成三種形狀。

### 一、排序後永遠選最早結束的

```python
intervals.sort(key=lambda x: x[1])   # 按結束時間，不是開始時間
end = float('-inf')
count = 0
for start, finish in intervals:
    if start >= end:                 # 不重疊才拿
        count += 1
        end = finish
```

交換論證：最早結束的那個留給後面的空間最大。把它換成任何一個結束更晚的，可選的區間只會變少不會變多。

**排序的 key 選錯就整題錯**，這是這類題唯一的難點 —— 而且端點相接算不算重疊要看題目（435 算不重疊，452 算重疊），差在 `>=` 還是 `>`。

例題：[435. Non-overlapping Intervals](/interview/coding/435-non-overlapping-intervals)、[452. Minimum Number of Arrows](/interview/coding/452-minimum-number-of-arrows-to-burst-balloons)、[1024. Video Stitching](/interview/coding/1024-video-stitching)、[253. Meeting Rooms II](/interview/coding/253-meeting-rooms-ii)

### 二、對撞時丟掉不可能更好的一邊

```python
left, right = 0, len(height) - 1
while left < right:
    ans = max(ans, min(height[left], height[right]) * (right - left))
    if height[left] < height[right]:
        left += 1        # 矮的那邊不可能再參與更好的答案
    else:
        right -= 1
```

交換論證：不管移動哪一邊，底邊都一定變短；而水位不可能超過現在較矮的那根。兩個因子都不可能變好，所以矮的那根可以安全丟掉。

這一類的貪心動作是**丟棄**而不是選取 —— 每一步安全地砍掉一個候選。

例題：[11. Container With Most Water](/interview/coding/11-container-with-most-water)、[870. Advantage Shuffle](/interview/coding/870-advantage-shuffle)

### 三、每次取極值（配 heap）

當「最好的選擇」會隨著每一步改變，就用 heap 動態維護：

```python
heapq.heapify(sticks)
while len(sticks) > 1:
    a = heapq.heappop(sticks)
    b = heapq.heappop(sticks)
    heapq.heappush(sticks, a + b)    # 合併後放回去，重新參與競爭
```

交換論證：先合併的成本會被後面每一次合併重複計入，所以短的一定要先合併。

**訊號是「排序一次不夠，因為選過之後順序會變」** —— 這時候 heap 才是對的資料結構，而不是先 `sort()`。

例題：[1167. Minimum Cost to Connect Sticks](/interview/coding/1167-minimum-cost-to-connect-sticks)、[1046. Last Stone Weight](/interview/coding/1046-last-stone-weight)、[1962. Remove Stones to Minimize the Total](/interview/coding/1962-remove-stones-to-minimize-the-total)

## 是 Greedy，還是只是「排序 + 掃一遍」

這兩件事長得很像，但只有前者需要證明：

| | 有沒有在做選擇 | 例子 |
|---|---|---|
| **是 Greedy** | 有候選被選中或被丟棄，選了就回不去 | [435](/interview/coding/435-non-overlapping-intervals)、[11](/interview/coding/11-container-with-most-water)、[122](/interview/coding/122-best-time-to-buy-and-sell-stock-ii)、[134](/interview/coding/134-gas-station) |
| **不是** | 每個元素都會被處理，輸出是被決定的 | [56. Merge Intervals](/interview/coding/56-merge-intervals)、[57. Insert Interval](/interview/coding/57-insert-interval)、[986. Interval List Intersections](/interview/coding/986-interval-list-intersections) |

56 沒有選擇 —— 它只是把資料換一種形狀輸出，所以它不需要交換論證，也不會有「貪錯」的風險。

同樣的道理解釋了股票家族的分界：[121](/interview/coding/121-best-time-to-buy-and-sell-stock) 只是在算前綴最小值，不是貪心；[122](/interview/coding/122-best-time-to-buy-and-sell-stock-ii) 每天在決定「這段漲幅吃不吃」，才是。

## 換了名字的貪心

有些演算法本質是貪心，只是有自己的名字，通常不會掛 Greedy 這個標籤：

- **MST** — Kruskal 每次挑最短的邊、Prim 每次挑最近的點，正確性靠 cut property，那就是交換論證。見 [1584. Min Cost to Connect All Points](/interview/coding/1584-min-cost-to-connect-all-points)、[1135. Connecting Cities](/interview/coding/1135-connecting-cities-with-minimum-cost)
- **Dijkstra** — 每次確定距離最小的點就永不再改
- **Huffman** — 就是上面第三種形狀

## 同一題的兩種寫法

這幾題 DP 和 Greedy 並排放最能看出差別：

| 題目 | DP 版本 | Greedy 版本 |
|---|---|---|
| [55. Jump Game](/interview/coding/55-jump-game) | 每個點問「從我出發能否到終點」，$O(n^2)$ | 只維護「能到的最遠處」，$O(n)$ |
| [53. Maximum Subarray](/interview/coding/53-maximum-subarray) | `dp[i] = max(dp[i-1] + num, num)` | 前綴為負就整段丟掉（Kadane） |
| [2244. Minimum Rounds](/interview/coding/2244-minimum-rounds-to-complete-all-tasks) | 記憶化拆解 2 和 3 | 直接算 $\lceil c/3 \rceil$ |

共同的模式是：**發現「怎麼走到這裡的」對後面沒有影響，狀態就從 $O(n)$ 塌成 $O(1)$。**

## 怎麼判斷能不能貪

順序是這樣：

1. **先花 30 秒找反例。** 這比想證明快得多，而且大部分想貪的直覺會在這裡被打掉。
2. **排序之後變簡單 → 通常可以貪。** 區間題、任務排程題幾乎都是「先排序，再一路掃」。
3. **選了之後剩下的問題跟原題同型 → 可以貪。** 這是最佳子結構。
4. **選擇會消耗「可互相取代的資源」→ 大概不能貪，要 DP。** 找零錢就是這種：4 和 3+1 都是 4 塊錢，但對後續的影響完全不同，你在當下無從判斷。

最實用的一條分界線：

**當「這一步選什麼」會改變「剩下能選什麼」的組合，就不能貪。**

更多題目 → [#Greedy](/interview/coding?tag=Greedy)

回到總索引 → [Coding Interview Preparation](/interview/coding/coding-interview-preparation)