算法面试突击手册 —— 贪心

---

一、概念与特点

大白话 + 类比

贪心 = 老鼠吃奶酪，每次只吃眼前最大的一块

一只老鼠在迷宫里找奶酪，每个房间都有几块。老鼠的策略是：每进一个房间，只挑最大的那块吃，吃完去下一个房间——从不后悔，从不回头。这就是贪心：每一步都选当前最优，相信局部最优最终就是全局最优。

贪心 vs 动规的关键区别：

• DP：回头看所有子问题，从多个候选中综合决策。“我该不该偷这家？先看看偷和不偷各自的总收益”
• 贪心：只看当前一步，做了决定就不后悔。“这家能偷就偷，不能就跳过，从不回头改主意”

贪心有门槛——不是所有局部最优都能推出全局最优。面试中的贪心题都有经过验证的正确性直觉，但难在”看出用贪心”这一步。

贪心的两大模式

模式	思路	代表题
直接贪心	遍历时维护一个”当前最优”状态，不断更新	买卖股票、跳跃游戏
排序 + 贪心	先按某种规则排序，然后按序贪心处理	划分字母区间、重建队列

核心特征（什么时候该想到用它）

特征	说明
选择后不可逆	每次选最优，没有任何回头操作
部分最优 → 全局最优	必须满足贪心选择性质（面试中通常有直观保证）
排序 + 贪心	先排序，再逐步贪心选择
维护最值/边界	跳跃游戏系列（维护最远可达）、买卖股票（维护最低价）
区间/划分	按结束时间排序 + 截断

识别信号词

• “最多”、“最少”、“最大利润” → 考虑能否贪心
• “跳跃”、“能否到达”、“最少步数” → 贪心维护最远可达
• “划分”、“截断”、“分成若干段” → 排序 + 贪心
• “安排”、“调度”、“重建队列” → 按规则排序 + 贪心插入
• “一次买卖” → 贪心维护历史最低价

贪心证明的常见直觉

面试中通常不需要严格数学证明，但要用直觉说服面试官：

1. 反证法直觉：“如果我不选当前最优，换成别的方案，结果不会更好”
2. 交换论证：“任意最优解都可以通过一系列交换变成贪心解，且结果不差”
3. 单调性：最优指标随着遍历单调递增/递减

---

二、Hot 100 精讲题目

---

121. Best Time to Buy and Sell Stock 买卖股票的最佳时机

📌 只能买卖一次，求最大利润。如 [7,1,5,3,6,4] → 5（第二天 1 买入，第五天 6 卖出）

🔍 解题分析

为什么用贪心

暴力法：枚举所有买卖日期对 O(n²)。贪心思路：如果我在每一天卖出，我肯定希望买入价是这天之前的最低价。所以我只要在遍历过程中维护”历史最低价”，每天算一次”今天卖出能赚多少”，沿途更新最大值即可。

贪心本质：每一步做两个决策——

• 如果今天价格比历史最低价还低 → 更新历史最低价（以后在更低点买入）
• 否则 → 算今天卖出的利润（当前价 - 历史最低价），更新最大利润

为什么这样不会错过最优解：最大利润的卖出日期一定是某一天。在那一天之前的最低买入价，一定在遍历到卖出日之前被我们记录过了。所以遍历每一天时计算的利润之一就是最终答案。

关键边界条件/易错点

易错点	说明
只有一天	不能买卖，利润为 0
价格一直跌	最大利润为 0（不买不卖），算法会自动处理：maxProfit 不会被更新
minPrice 初始值	用 Integer.MAX_VALUE 而不是 0，因为股票价格都是正数
先更新 minPrice 还是先算利润	先更新 minPrice 再算利润也没问题，因为当天买入卖出利润为 0，不影响答案

✅ 完整 Java 实现

public int maxProfit(int[] prices) {
    // 历史最低买入价，初始化为极大值
    int minPrice = Integer.MAX_VALUE;
    // 最大利润，初始为 0（可以不交易）
    int maxProfit = 0;

    for (int price : prices) {
        // 决策一：今天是不是更低的买入时机？
        if (price < minPrice) {
            minPrice = price; // 更新最低价，以后可以在这个更低点买
        }
        // 决策二：如果在历史最低价买入、今天卖出，能赚多少？
        int profit = price - minPrice;
        if (profit > maxProfit) {
            maxProfit = profit; // 更新最大利润
        }
    }

    return maxProfit;
}

手算验证：prices = [7, 1, 5, 3, 6, 4]

i	price	minPrice	profit = price - minPrice	maxProfit
1	7	7	0	0
2	1	1	0	0
3	5	1	4	4
4	3	1	2	4
5	6	1	5	5
6	4	1	3	5

最终 maxProfit = 5（1 买 6 卖）。

⏱ 复杂度分析

• 时间复杂度：O(n) —— 一次遍历，每步 O(1)
• 空间复杂度：O(1) —— 只用了两个变量

💡 记忆口诀

“每天假装今天卖，回头看历史最低价；赚钱就更新，跌了更新买点”

---

55. Jump Game 跳跃游戏

📌 数组 nums[i] 表示在位置 i 能跳的最大步数。判断能否从下标 0 跳到最后一个下标。如 [2,3,1,1,4] → true；[3,2,1,0,4] → false

🔍 解题分析

为什么用贪心

不需要知道具体走哪条路，只需要知道”我能到达的区域”的右边界在哪。维护一个 farthest：在遍历过程中，每一步更新”我能到的最远位置”。如果遍历超过了 farthest，说明当前区域到不了，返回 false。

贪心本质：我们把跳跃看作”不断扩张能到达的领土”。在到达当前领土的边界之前，我们不断用更远的跳跃来扩张领土的右边界。当领土覆盖最后一个下标时就是成功；如果领土不再扩张且还没到终点，就是失败。

核心思路（步骤化）

1. 初始化 farthest = 0（当前能到达的最远位置）
2. 遍历数组每个位置 i：
   • 如果 i > farthest → 当前位置永远到不了 → 返回 false
   • 否则更新 farthest = max(farthest, i + nums[i])
   • 如果 farthest >= n-1 → 提前返回 true

关键边界条件/易错点

易错点	说明
单元素数组	[0] → true（已经在终点），循环不执行直接返回 true
中途卡住	[0, 1] → false（第一步就跳不动），i=0 时 farthest=0，i=1 时 i > farthest
刚好到终点	[2, 0, 0] → farthest 在 i=0 时为 2，刚好覆盖 n-1=2
贪心不能求具体路径	这解法只回答”能否到达”，不回答”走哪条路”

类比：你是加油站老板，每到一个地方就扩张油管能输送的范围。油管能铺到的最远处就是你的势力范围。如果走到范围边界还没铺过去，就 stuck 了。

✅ 完整 Java 实现

public boolean canJump(int[] nums) {
    // 当前能到达的最远位置
    int farthest = 0;
    int n = nums.length;

    // 遍历每个位置，同时 farthest 不断更新
    for (int i = 0; i < n; i++) {
        // 如果当前位置已经超过了能到达的最远范围，说明到了了这里
        if (i > farthest) {
            return false;
        }

        // 从当前位置能跳多远？更新最远范围
        farthest = Math.max(farthest, i + nums[i]);

        // 提前终止：已经能到终点了
        if (farthest >= n - 1) {
            return true;
        }
    }

    return true; // 遍历完都没被卡住，能到
}

手算验证：nums = [2, 3, 1, 1, 4]

i	i ≤ farthest?	nums[i]	i + nums[i]	farthest	farthest ≥ 4?
0	✓ (0≤0)	2	2	2	✗
1	✓ (1≤2)	3	4	4	✓ → true

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

i	i ≤ farthest?	nums[i]	i + nums[i]	farthest
0	✓	3	3	3
1	✓	2	3	3
2	✓	1	3	3
3	✓	0	3	3
4	✓	—	—	3（不能到 4）→ 但这里因为 i≤farthest 一直成立，循环跑完了，最终 farthest=3 < n-1

需要在循环中检查是否到了终点。上面代码中到了 i=3 时 farthest=3，遍历完返回 true 但其实 farthest 只有 3。需在最后判断 farthest >= n-1。

实际上代码第 22 行的提前返回已经够了（farthest >= n-1 才会 return true），最后 return false：

public boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;      // 当前位置够不着
        farthest = Math.max(farthest, i + nums[i]);
        if (farthest >= nums.length - 1) return true; // 提前成功
    }
    return false;
}

⏱ 复杂度分析

• 时间复杂度：O(n) —— 一次遍历，每步 O(1)
• 空间复杂度：O(1) —— 只用了 farthest 变量

💡 记忆口诀

“边走边扩张领土，走到够不着的地方就失败；能覆盖终点就成功”

---

45. Jump Game II 跳跃游戏 II

📌 每个元素代表最大跳跃长度。求到达终点的最少跳跃次数。题目保证一定能到达。如 [2,3,1,1,4] → 2（0→1→4 两跳）

🔍 解题分析

为什么用贪心

贪心策略：每次跳跃的落点选择，不要纠结具体落在哪，而是看”这次跳跃的范围内，能让下一次跳最远的那个位置”。因为我们总是希望少跳几次，所以每次跳都要选能让后续覆盖最远的那个落点。

核心思路——“分层跳跃”

把跳跃过程看作一层一层推进：

• 第 0 层：起点（下标 0）
• 第 1 层：从起点一跳能到达的所有位置
• 第 2 层：从第 1 层任意位置再跳一次能到达的所有位置
• ……

每当我们走完当前层的最后一个位置时，就必须再跳一次才能继续前进。这个”跳一次”意味着进入下一层。

核心思路（步骤化）

1. 维护三个变量：
   • jumps：已跳跃次数
   • curEnd：当前跳跃能到达的最远边界（当前层的右边界）
   • curFarthest：在当前位置之前的所有位置中，能到达的最远距离（下一层的候选右边界）
2. 遍历数组（到 n-2 即可，不需要到最后一个元素，因为到达终点不需要再跳）：
   • 更新 curFarthest = max(curFarthest, i + nums[i])
   • 如果 i 走到了 curEnd（当前层的末尾）：
     • jumps++（必须跳一次了）
     • curEnd = curFarthest（下一层的新边界）
3. 返回 jumps

类比：就像蛙跳比赛。第一跳能跳到 A 范围内的任意位置。在 A 范围内的每个位置，你都在心里计算”如果我在这个位置起跳，最远能到哪”。A 范围走完后，你就知道自己第二跳最多能到哪了。这种”走一层算下一层”的方式保证了你总用最少的跳跃次数。

关键边界条件/易错点

易错点	说明
循环到 n-2	不需要遍历最后一个元素，因为到达终点后不需要再跳。如果遍历到 n-1，curEnd 恰好等于 n-1 时会多做一次不必要的跳跃
单元素数组	[0] → 0 跳（已经在终点），因为循环不执行
curFarthest ≥ n-1 时	可以提前返回，因为下一跳必定能到终点
和 55 题的区别	55 题问”能不能”，45 题问”最少几次”，后者需要分层

为什么贪心是对的：在任何一层中，你选择在哪跳不重要。重要的是”这一层能覆盖的范围内，下一层能覆盖到多远”。因为不管你选哪个中间落点，最终你都要再跳一次，而下一跳能覆盖的越远，用的总步数就越少。

✅ 完整 Java 实现

public int jump(int[] nums) {
    // 每次跳跃能到达的最远边界（当前层的右边界）
    int curEnd = 0;
    // 在 curEnd 之前的所有位置中，下一次跳跃能到的最大位置
    int curFarthest = 0;
    // 已完成的跳跃次数
    int jumps = 0;

    // 注意：只遍历到 n-2，不需要访问最后一个元素
    // 因为到达最后一个元素时已经完成目标，不需要再跳
    for (int i = 0; i < nums.length - 1; i++) {
        // 在当前层内，不断更新"下一层"能到达的最远位置
        curFarthest = Math.max(curFarthest, i + nums[i]);

        // 走到了当前层的末尾 → 必须跳一次进入下一层
        if (i == curEnd) {
            jumps++;                  // 跳！
            curEnd = curFarthest;     // 更新下一层的边界

            // 如果下一跳已经能到终点，提前结束
            if (curEnd >= nums.length - 1) {
                break;
            }
        }
    }

    return jumps;
}

手算验证：nums = [2, 3, 1, 1, 4]

i	nums[i]	i+nums[i]	curFarthest	i == curEnd?	jumps	curEnd
0	2	2	2	✓ (i==0)	1	2
1	3	4	4	✗ (i==1≠2)	1	2
2	1	3	4	✓ (i==2)	2	4

curEnd=4 ≥ n-1=4，break。最终 jumps=2。

⏱ 复杂度分析

• 时间复杂度：O(n) —— 一次遍历，每步 O(1)
• 空间复杂度：O(1) —— 只用了三个变量

💡 记忆口诀

“把跳跃分层次，走完当前层必跳一次，同时算好下一层的边界”

---

763. Partition Labels 划分字母区间

📌 将字符串划分为尽可能多（注意：是”多”不是”少”）的片段，使同一字母只出现在一个片段中。返回每个片段的长度。如 "ababcbacadefegdehijhklij" → [9,7,8]

🔍 解题分析

为什么用贪心

题目要求”划分尽可能多的片段”——这就是贪心的目标。我们需要找到切割点：在某个位置切下去之后，左边所有字母在右边都不再出现。

贪心策略：维护当前片段”必须延伸到的位置”（需要包含所有已出现字母的最后位置）。当遍历到的位置等于这个”必须延伸到的位置”时，说明后面不会再出现当前片段内的任何字母——立刻在此处截断。

核心思路（步骤化）

1. 预处理：遍历字符串，用 int[26] 记录每个字母最后出现的位置
2. 再次遍历，维护两个变量：
   • start：当前片段的起始位置
   • curEnd：当前片段必须延伸到的最远位置
3. 每到一个字符，curEnd = max(curEnd, 该字符最后出现的位置)
4. 当 i == curEnd 时：
   • 当前片段长度 = i - start + 1，加入结果
   • start = i + 1，开始新片段

关键边界条件/易错点

易错点	说明
贪心目标理解	题目说”尽可能多”，所以每次遇到可以切的位置就立刻切，不要贪”更长的片段”
字符最后位置的预处理	第一遍扫描记录最后位置，第二遍才是贪心分割
片段不能有交集	start 必须紧随上一个片段之后

类比：就像给字母圈领地。A 第一次出现在位置 0，最后一次在位置 8。那么在位置 8 之前的所有字母，如果它们的最后位置超过了 8，就必须把领地扩大到那个位置。当走到一个位置，当前领地内所有字母的”最后一次出现”都不超过这个位置时，说明领地可以闭合了——果断切一刀。

✅ 完整 Java 实现

public List<Integer> partitionLabels(String s) {
    // 1. 预处理：记录每个字母最后出现的位置
    int[] lastPos = new int[26];
    for (int i = 0; i < s.length(); i++) {
        lastPos[s.charAt(i) - 'a'] = i;
    }

    List<Integer> result = new ArrayList<>();
    int start = 0;      // 当前片段起始下标
    int curEnd = 0;     // 当前片段必须至少延伸到的位置

    // 2. 贪心扫描：找切割点
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 扩大当前片段的"必要范围"
        // 因为字符 c 的最后一次出现在 lastPos[c]，所以当前片段至少要延伸到那里
        curEnd = Math.max(curEnd, lastPos[c - 'a']);

        // 当前位置恰好是片段的必要边界 → 切！
        if (i == curEnd) {
            result.add(i - start + 1); // 记录片段长度
            start = i + 1;             // 下一个片段的起始
            // curEnd 在下一轮迭代中自动被新字符更新
        }
    }

    return result;
}

手算验证：s = "ababcbacadefegdehijhklij"（简要版）

第一遍扫描后 lastPos：a→8, b→5, c→7, d→14, e→15, f→11, g→13, h→19, i→22, j→23, k→20, l→21。

第二遍扫描贪心：

| 片段1 (ac) | i 走到 8 时 curEnd=8，切！长度 9 | | 片段2 (de) | i 走到 15 时 curEnd=15，切！长度 7 | | 片段3 (h~l) | i 走到 23 时 curEnd=23，切！长度 8 |

结果 [9, 7, 8]。

⏱ 复杂度分析

• 时间复杂度：O(n) —— 两遍独立扫描，每遍 O(n)
• 空间复杂度：O(1) —— int[26] 是固定大小

💡 记忆口诀

“先看每个字母最后一次在哪，再贪心扫一遍；走到必须停的位置就切一刀”

---

406. Queue Reconstruction by Height 根据身高重建队列

📌 给定 people[i] = [hᵢ, kᵢ]，hᵢ 是身高，kᵢ 是这个人前面有 kᵢ 个身高 ≥ hᵢ 的人。打乱顺序后，重建原始队列。如 [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] → [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

🔍 解题分析

为什么用贪心

这是一道经典的”排序 + 贪心插入”题。

核心洞察：先处理高的人，再处理矮的人。因为：

• 高的人看不到矮的人（矮的人不影响高的人的 k 值）
• 矮的人可以看到高的人（高的人已经排好，矮的人前面有多少更高的已经固定）
• 所以高的人先按 k 站在正确位置；矮的人后来插入时，因为前面所有人都比自己高（或一样高），它的 k 值直接就是它应该插入的下标

核心思路（步骤化）

1. 排序：身高从高到低；身高相同的，k 从小到大（k 小的先站）
2. 遍历排序后的 people，对于每个人 [h, k]：
   • 将其插入到结果列表的第 k 个位置
   • 因为此时列表中所有人身高都 ≥ h，所以前面恰好有 k 个不比它矮的人
3. 返回列表

为什么插入操作是安全的：插入一个矮个子到 k 位置，它右边所有高个子都被挤后了一位——但这对高个子没有影响，因为矮个子不会增加高个子”前面更高的人数”。

关键边界条件/易错点

易错点	说明
排序规则	身高降序是必须的；身高相同时 k 升序，否则可能插入越界
ArrayList 的 add(index, val)	是 O(n) 操作（需要移动元素），最终 O(n²)，但在数据量合理时可以接受
为什么不按 k 排序	如果先处理矮的，后续插入高的会破坏矮的 k 值

类比：就像一群人按身高从高到矮顺序入场。高个子先站，每个人根据自己的 k 值直接走到队伍里对应的空位（因为前面的人都比他高）。矮个子后来插入时，“前面有几个更高的人”已经被高个子们固定了——插进去就行，不影响任何人。

✅ 完整 Java 实现

public int[][] reconstructQueue(int[][] people) {
    // 第一步：排序
    // 规则1：身高从高到低（b[0]-a[0]）
    // 规则2：身高相同的，k 从小到大（a[1]-b[1]）
    // 为什么身高相同要按 k 升序？保证插入时 k 是合法下标
    Arrays.sort(people, (a, b) -> {
        if (a[0] != b[0]) {
            return b[0] - a[0]; // 身高降序
        }
        return a[1] - b[1];     // k 升序
    });

    // 第二步：按 k 插入
    // 遍历时，列表中已有的人身高都 ≥ 当前人
    // 所以当前人的 k 值恰好等于他在列表中应该插入的下标
    List<int[]> list = new ArrayList<>();
    for (int[] person : people) {
        // 插入到第 k 个位置（k = person[1]）
        // 插入后，这个位置前面恰好有 k 个人身高 ≥ person[0]
        list.add(person[1], person);
    }

    // 第三步：转为数组返回
    return list.toArray(new int[people.length][2]);
}

手算验证：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

排序后：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

插入的人	k	列表状态
[7,0]	0	[[7,0]]
[7,1]	1	[[7,0],[7,1]]
[6,1]	1	[[7,0],[6,1],[7,1]]
[5,0]	0	[[5,0],[7,0],[6,1],[7,1]]
[5,2]	2	[[5,0],[7,0],[5,2],[6,1],[7,1]]
[4,4]	4	[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

验证：[5,0] 前面 0 个更高的 ✓，[7,0] 前面 0 个更高的 ✓，[5,2] 前面有 [7,0] 和 [7,0]？其实前面有 5,0 不算、[7,0] 算，所以是 2 个 ✓。

⏱ 复杂度分析

• 时间复杂度：O(n²) —— 排序 O(n log n)，每步 list.add(index, val) 平均 O(n)，共 n 次
• 空间复杂度：O(n) —— ArrayList 存 n 个元素

💡 记忆口诀

“高个先排队，矮个根据 k 直接插队；身高降序排，k 升序来”

---

🔜 上一章：11-动态规划 | 下一章：13-图