Go back

LeetCode Hot 100——贪心篇（买卖股票、跳跃游戏、区间划分）

LeetCode Hot 100 · 贪心篇

贪心算法的核心套路只有一句话：每一步都做「当前看起来最优」的选择，并证明局部最优能推出全局最优。

在面试手撕场景里，贪心题真正的难点从来不是代码（贪心代码通常都很短），而是你凭什么敢这么贪——为什么这样选一定对？为什么不会漏掉更优解？以及那些一贪就错的边界。

Hot 100 里贪心分类共 4 道题，正好覆盖了贪心最常见的四种形态：

  1. 121. 买卖股票的最佳时机 —— 一次遍历维护「历史极值」
  2. 55. 跳跃游戏 —— 贪心维护「最远可达位置」（可行性判断）
  3. 45. 跳跃游戏 II —— 贪心按「轮次」扩展（最少步数）
  4. 763. 划分字母区间 —— 贪心做「区间合并/切分」

下面逐题拆解，每道题都从题意、难点易错点，到暴力解法、最优解、多解法对比、CodeTop 真实变体，一路走到底。

#121 买卖股票的最佳时机

题意

给定每天股票价格数组 prices，你只能完成一笔交易（一次买入、一次卖出），返回最大利润；若不能盈利则返回 0。

输入：prices = [7,1,5,3,6,4]
输出：5 （第 2 天买入价格 1，第 5 天卖出价格 6，利润 6-1=5）

难点与易错点

  1. 只能交易一次，不能反复买卖。利润必须是「某个卖出日 - 某个更早的买入日」，所以本质是找一个 (买入日 i, 卖出日 j) 且 i < j，使 prices[j] - prices[i] 最大。很多人一上来就想「低买高卖多次累加」，那是 122 题，不是这题。
  2. 为什么局部最优能推出全局最优：这是本题最关键的论证点。假设我们已经遍历到第 i 天，历史最低买入价是 minPrice。对于「在第 i 天卖出」这个决策，最大利润必然等于 prices[i] - minPrice（因为卖出价已定，买入价越低越好，而能选的最低价就是历史最低）。于是全局答案就是所有「在第 i 天卖出的最优利润」的最大值。贪心「每个卖出日都搭配历史最低买入价」之所以不漏解，是因为任何一个最优解的卖出日 j，其对应的最优买入日一定是 [0, j) 里的最低价——这正是遍历时维护 minPrice 覆盖到的。
  3. 边界/易错细节：
    • minPrice 初值必须设成 Integer.MAX_VALUE 或 prices[0]，否则第一天会被误判。
    • maxProfit 初值为 0（题目要求「不能盈利则返回 0」，所以不能初始化成 Integer.MIN_VALUE）。
    • minPrice 只能来自「今天及更早」的价格，遍历顺序天然保证了不会把明天的价格算进买入价。

解法一：暴力 / 直观

枚举所有「买入日 i、卖出日 j（j > i）」的二元组，取利润最大值。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int maxProfit = 0;
        // 枚举买入日 i 和卖出日 j，要求 i < j
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
            }
        }
        return maxProfit;
    }
}

复杂度推导：

瓶颈：对每个卖出日 j，都从头重新扫了一遍历史最低价，重复计算严重。观察发现「第 j 天的历史最低价」完全可以由「第 j-1 天的历史最低价」递推得到，不需要重新扫一遍——这就是下一步优化的切入点。

解法二：优化 / 最优（贪心）

题目本质：一次遍历维护「最低买入价」。记录历史最低价 minPrice，每天计算「今天卖出的利润」并更新最大值。

现实类比：炒股策略——每天看当前价，如果比历史最低价还低就更新「最佳买入点」，否则计算「今天卖出能赚多少」，取全局最大值。

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice  = Integer.MAX_VALUE; // 历史最低买入价
        int maxProfit = 0;                 // 全局最大利润

        for (int price : prices) {
            minPrice  = Math.min(minPrice, price);              // 更新历史最低买入价
            maxProfit = Math.max(maxProfit, price - minPrice);  // 今天卖出 vs 历史最优
        }

        return maxProfit;
    }
}

> **💭 思考**：为什么买卖股票一次交易能贪心，核心的「维护历史最低价」是怎么来的？一步步想——暴力枚举所有 (买入日, 卖出日) 的瓶颈是「对每个卖出日都从头重扫历史最低价」，重复计算严重。观察发现「第 j 天的历史最低价」可以由「第 j-1 天的」递推得到：`minPrice = min(minPrice, price)`。于是把「求前缀最小值」从每次 O(n) 降到增量 O(1)，一趟扫描就得到全局最大利润。贪心的依据是：卖出日一旦固定，最优买入日必然是它的前缀最低价，所以维护 `minPrice` 不会漏解。

复杂度逐步推导：

多解法对比

解法时间复杂度空间复杂度适用场景
暴力枚举二元组O(n²)O(1)仅用于验证思路；n > 1e4 就超时
贪心（一次遍历维护最低价）O(n)O(1)本题最优；Hot 100 标准答案

为什么选贪心：本题约束 n 可达 1e5，暴力 O(n²) 会超时（约 1e10 次运算）。贪心只需一遍扫描，且无额外空间。更重要的是它给出了「最优解结构」的证明——全局最优 = 每个卖出日搭配其前缀最低价的最大值，这个结构让贪心既是充分又是必要的。

CodeTop 变体

本题是「股票买卖系列」的入门题，字节/阿里高频追问方向是交易次数限制的推广：

面试官真实追问通常是：「如果允许两次交易呢？」→ 直接手写 123 的状态机；「为什么贪心不能直接套到两次交易？」→ 因为两次交易的最优决策不满足「只维护一个前缀最低价」这种一维极值结构，需要 DP。

#55 跳跃游戏

题意

给定数组 nums，nums[i] 表示在位置 i 最多能跳跃的步数（可以跳 1..nums[i] 任意步）。判断能否到达最后一个位置。

输入：nums = [2,3,1,1,4]  →  true
输入：nums = [3,2,1,0,4]  →  false（卡在位置 3，nums[3]=0 无法前进）

难点与易错点

  1. 「最多跳 nums[i] 步」≠「必须跳 nums[i] 步」。这是最容易理解错的地方。每个位置是一个范围（[i, i+nums[i]] 内任意点都可到达），而不是只能跳到 i + nums[i] 这一个点。理解成「范围」后，贪心才有依据。
  2. 为什么局部最优能推出全局最优：维护 maxReach = 目前所有可达位置能延伸出的最远下标。关键不变量：[0, maxReach] 区间内的每一个位置都必然可达。证明：能到达 maxReach 的那条路径经过某个位置 p，而 p 可达意味着它之前也有一条完整路径，归纳下去整条路径都在 [0, maxReach] 内。于是只要遍历过程中 i 始终不超过 maxReach，终点 n-1 一旦落入 maxReach 就可达。贪心每次取「能跳得最远」的选择，不会漏解——因为跳到更近的位置，其「未来能到的最远」一定不超过「当前最远 + 该点步数」的更新值，而 maxReach 已经把这个最大值收进了区间的并集。
  3. 边界/易错细节：
    • 判断 i > maxReach 必须在更新之前，否则可能用「尚未到达」的位置去扩展。
    • 空数组 / 单元素数组（nums=[0]）返回 true（已经在终点）。
    • 有人写成「必须恰好跳到 n-1」，但实际只要 maxReach >= n-1 即可提前返回 true，无需遍历到最后一格。

解法一：暴力 / 直观（回溯 / BFS / DP）

思路：把每个位置看成图的节点，从 i 能连到 [i+1, i+nums[i]] 的所有节点，问 0 能否到 n-1。用 BFS 最直观。

import java.util.*;

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] visited = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        visited[0] = true;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (cur == n - 1) return true; // 到达终点
            // 尝试从 cur 跳到它能到的每个位置
            for (int next = cur + 1; next <= Math.min(n - 1, cur + nums[cur]); next++) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        return false; // 队列空仍未到终点，说明不可达
    }
}

复杂度推导：

解法二：优化 / 最优（贪心）

题目本质：贪心维护「最远可达位置」。遍历时维护当前能到达的最远下标 maxReach，若当前下标超出 maxReach 则无法继续。

现实类比：过河跳石头——从每块石头能跳一段距离，维护目前能踩到的最远石头位置；走到某块石头时若它超出最远位置，就说明掉水里了。

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0; // 当前能到达的最远下标

        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false; // 当前位置超出可达范围，无法继续

            maxReach = Math.max(maxReach, i + nums[i]); // 更新最远可达位置
            if (maxReach >= nums.length - 1) return true; // 提前到达终点
        }

        return true;
    }
}

> **💭 思考**：为什么「能否到达」用一个 `maxReach` 就够，而不是 BFS 逐点展开？一步步想——BFS 把每个位置看成节点、枚举每个可达后继，瓶颈是「只关心最远到哪，却逐点枚举所有后继」，边数可达 O(n²)。想清楚问题只问「能不能到」，只需维护一个上界：`[0, maxReach]` 内每个位置都可达（连续区间），所以每到一个位置，只需用它更新 `maxReach = max(maxReach, i + nums[i])`。一旦 `i > maxReach` 就是断点，`maxReach >= n-1` 就是到达。把「逐点搜索」压缩成「维护一个覆盖上界」，就是可行性判断的贪心。

复杂度逐步推导：

多解法对比

解法时间复杂度空间复杂度适用场景
BFS（图搜索）O(n²)O(n)需要打印「具体一条路径」时
贪心（最远可达）O(n)O(1)只判断「能否到达」，Hot 100 标准答案

为什么选贪心：本题只问「能不能到」，不问「怎么到、走几步」。可行性判断天然适合贪心——只要维护一个「覆盖上界」就能回答。BFS 的额外信息（具体路径）在这里是浪费。约束下 n 可达 1e4，BFS 的 O(n²) 可能超时，贪心 O(n) 秒出。

CodeTop 变体

面试常见追问：「为什么 55 能贪心，1306 不能？」→ 因为 55 的移动范围是单调向前的连续区间，可达集合始终保持 [0, maxReach] 的连续形态；而 1306 允许回跳，可达集合会「断断续续」，必须逐点搜索。

#45 跳跃游戏 II

题意

给定 nums（题目保证一定可以到达最后位置），返回到达最后一个位置所需的最少跳跃次数。

输入：nums = [2,3,1,1,4]
输出：2（0 -> 1 -> 4）

难点与易错点

  1. 贪心不能「每一步都选当前最远」。这是本题最大的坑。反例 nums = [3,4,2,1,0,4]：从 0 若直接跳 3 步到位置 3（nums[3]=1），再到 4，步数反而更多；正确是从 0 跳 1 步到 1（nums[1]=4）再直达。所以「当前点跳得最远」的局部贪心是错的——正确做法是先看清当前这一跳能覆盖的范围，再在范围内选「下一跳能延伸最远」的点。
  2. 为什么「按批次扩展」的局部最优能推出全局最优：把跳跃过程分层（类似 BFS 按层）。设 end 为「上一跳能覆盖到的边界」，maxPos 为「在 [当前批, end] 范围内，所有点能延伸出的下一跳最远位置」。任何到达终点的路径，其每一跳的落点都落在某一层内；要步数最少，等价于每一层都「跳到能让我下一层覆盖最远的那个落点」。因为题目保证可达，按「层边界」计数就能保证每一步都不浪费。这是贪心（取最大延伸）与 BFS（按层）的杂交，正确性来源是可达区间连续且单调向前。
  3. 边界/易错细节：
    • 遍历只到 n-1，不包含最后一个元素：因为到达 n-1 时已经结束，不需要再跳。若把最后元素也纳入循环，会在 i == end 时多计一次 ans。
    • 更新 end = maxPos 的时机是 i == end，此时「当前批」已扫完，才把下一批边界替换进来。
    • 单元素数组 nums=[0] 应返回 0（已经在终点，无需跳），循环 for i < 0 直接不执行，ans=0，天然正确。

解法一：暴力 / 直观（DP）

dp[i] 表示跳到位置 i 的最少步数，用「谁能在一步内跳到 i」来转移。

import java.util.*;

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // 起点 0 步

        for (int i = 1; i < n; i++) {
            // 找所有 j < i 且 j + nums[j] >= i，取 dp[j] 最小
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

复杂度推导：

解法二：优化 / 最优（贪心 + BFS 分层）

题目本质：贪心按轮次扩展。将跳跃过程分成「轮次」（类似 BFS 按层），维护本轮覆盖终点 end 和下一轮终点 maxPos，每次到达 end 时必须跳（ans++）。

现实类比：公交路线接驳——第一趟车覆盖最远距离，第一趟覆盖范围内所有站都可以换乘第二趟，选覆盖最远的那趟换乘。

class Solution {
    public int jump(int[] nums) {
        int end    = 0; // 当前跳跃批次的终点
        int maxPos = 0; // 下一跳能到达的最远位置
        int ans    = 0; // 跳跃次数

        // 不遍历最后一个元素（到达最后一步时无需再跳）
        for (int i = 0; i < nums.length - 1; i++) {
            maxPos = Math.max(maxPos, i + nums[i]); // 更新下一批次可到最远

            if (i == end) { // 到达当前批次终点，必须跳一次
                ans++;
                end = maxPos; // 更新下一批次终点
            }
        }

        return ans;
    }
}

> **💭 思考**：为什么 45 题不能「每步都跳最远」，正确贪心是什么？一步步想——DP 的瓶颈是「对每个 i 回头找最优前驱」，O(n²)。想一次扫描，直觉是「每步跳最远」，但反例 `[3,4,2,1,0,4]` 说明跳到当前最远可能落到 `nums` 很小、后续无力的点。正确做法是把跳跃分层（像 BFS 按层）：用 `end` 标记当前这一跳能覆盖的边界，`maxPos` 记录该范围内所有点能延伸出的最远位置，扫到 `end` 时就必须跳一次、更新 `end = maxPos`。这贪的是「在当前覆盖范围内选能让下一层最远的点」，层数就是最少步数——可达区间连续且单调向前，是它能贪的根因。

复杂度逐步推导：

多解法对比

解法时间复杂度空间复杂度适用场景
DP（dp[i] 最少步数）O(n²)O(n)通用、好理解，但 n 大时超时
贪心（按批次扩展）O(n)O(1)本题最优；Hot 100 标准答案

为什么选贪心：约束 n 可达 1e4，DP 的 O(n²) 约 1e8，勉强或超时；贪心 O(n) 干净利落。且贪心把「最少步数」翻译成「最少层数」，这个分层视角是面试官最想听到的洞察——它同时解释了对错两个贪心版本的差异。

CodeTop 变体

#763 划分字母区间

题意

字符串 s 由小写字母组成，将其划分为尽可能多的片段，同一字母只能出现在一个片段中，返回每个片段的长度。

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：划分为 "ababcbaca"、"defegde"、"hijhklij" 三段，同一字母不会跨段出现。

难点与易错点

  1. 「同一字母只出现在一个片段」是硬约束。这意味着如果一个字母首次出现在片段 A、最后一次出现在很后面，那么 A 必须一直延伸到那个最后出现位置，中途所有字母都被卷入。这是「区间必须闭合」的连锁反应，也是贪心的核心。
  2. 为什么局部最优能推出全局最优：先记录每个字符的最后出现位置 last[]。从左到右扫，维护当前片段右边界 end = max(end, last[s[i]])。当 i == end 时切分。正确性：end 是「当前片段内所有已出现字符的最后位置最大值」，在 i < end 时切分会导致某个已出现的字符在后续片段重复出现（违约）；在 i == end 时切分则当前片段内所有字符都不会再出现，此时立即切分能保证「片段数最多」（尽早闭合 = 给后续片段留更多切分机会，这正是「尽可能多」的贪心点）。
  3. 边界/易错细节：
    • last[] 大小固定 26（小写字母），索引用 s.charAt(i) - 'a'。
    • 切分后 start = i + 1，片段长度是 end - start + 1（用更新前的 start 算）。
    • 最后一段一定会在 i == end 时闭合（因为最后一个字符的 last 就是它自己），不会漏。
    • 返回的是每段长度的列表，不是片段字符串本身。

解法一：暴力 / 直观（区间合并）

思路：把每个字母抽象成一个区间 [first, last]（该字母首次和最后出现位置）。题目约束「同字母不分片」等价于「这些区间不能交叉切割」，因此可以先收集所有字母区间，再按「合并重叠区间」的方式合并，最后输出每个合并区间的长度。

import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String s) {
        int n = s.length();
        // 收集每个字母的 [first, last] 区间
        int[] first = new int[26];
        int[] last  = new int[26];
        Arrays.fill(first, -1);
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            if (first[c] == -1) first[c] = i; // 首次出现
            last[c] = i;                       // 最后出现
        }

        // 收集所有出现过的字母的区间
        List<int[]> intervals = new ArrayList<>();
        for (int c = 0; c < 26; c++) {
            if (first[c] != -1) intervals.add(new int[]{first[c], last[c]});
        }
        intervals.sort((a, b) -> a[0] - b[0]); // 按起点排序

        // 合并重叠区间
        List<Integer> result = new ArrayList<>();
        int start = intervals.get(0)[0];
        int end   = intervals.get(0)[1];
        for (int[] it : intervals) {
            if (it[0] > end) { // 无重叠，闭合上一段
                result.add(end - start + 1);
                start = it[0];
                end = it[1];
            } else { // 有重叠，扩展右边界
                end = Math.max(end, it[1]);
            }
        }
        result.add(end - start + 1); // 最后一段
        return result;
    }
}

复杂度推导：

解法二：优化 / 最优（贪心，一次扫描维护右边界）

题目本质：贪心区间合并。先记录每个字符最后出现位置 last[]，再遍历字符串，每个片段右边界为当前所有已出现字符的最晚位置的最大值，遇到右边界就切分。

现实类比：装箱分组——要把同类型物品放入同一箱子，先记好每种物品最后一个在哪；当前箱子装到某位置时，若所有已装物品都在这里截止，就封箱。

import java.util.*;

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

        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']); // 扩展当前片段终点

            if (i == end) { // 到达片段终点，切分
                result.add(end - start + 1);
                start = i + 1; // 下一片段开始
            }
        }

        return result;
    }
}

> **💭 思考**：为什么这题能跳过「收集区间再合并」，直接一次扫描边扩展边切分？一步步想——区间合并法先把每个字母抽象成 `[first, last]` 再排序合并，虽然也 O(n)，但多了排序和区间构造的冗余。关键洞察是：扫描顺序天然就是「区间起点有序」，所以只要先记好每个字符的最后出现位置 `last[]`，遍历时维护 `end = max(end, last[s[i]])`，当 `i == end` 时当前片段内所有字符都不再出现，立刻切分——既满足「同字母不分片」的硬约束，又因为「尽早闭合」而保证片段数最多。边扫边扩展边切分，一步到位。

复杂度逐步推导：

多解法对比

解法时间复杂度空间复杂度适用场景
区间合并（排序后 merge）O(n + 26 log 26)O(1)需要显式给出每个字母区间时
贪心（一次扫描维护右边界）O(n)O(1)本题最优；Hot 100 标准答案

为什么选贪心：解法一虽然也是 O(n)（因字母表固定），但它把问题抽象成「区间合并」再绕回来，代码冗长且易在边界出错。贪心解法直接利用「扫描顺序天然就是区间起点有序」这一性质，边扫边扩展边切分，一次线性扫描完成，是这题最优雅、也最不容易写错的写法。

CodeTop 变体

本题是「区间贪心」家族的一员，字节/美团高频的延伸方向是区间调度类：

面试常见追问：「763 和 452 的贪心区别在哪？」→ 763 贪的是「尽早切分」（维护区间右边界，扫到就切），452/435 贪的是「按右端点排序后尽量共用」（排序 + 比较下一段起点）。两者都是「右边界」驱动，但一个做切分、一个做选点。

以上四题覆盖了贪心在 Hot 100 里的四种典型套路：维护历史极值（121）、维护可达上界（55）、按批次分层扩展（45）、区间右边界驱动切分（763）。手撕时牢记两点即可：一是先用一句话说清「局部最优为何能推出全局最优」，二是把边界（初值、循环范围、更新时机）抠死。

章末提问

  1. #121 凭什么「每个卖出日配历史最低买入价」就能得到全局最优？——结论：因为卖出日一旦固定，买入价越低利润越大，而能选的最低价就是前缀最低价；全局最优解里，任意一个最优卖出日的买入日必然是其前缀最低价，所以遍历时维护 minPrice 不会漏解。
  2. #45 为什么不能「每步都跳最远」，正确贪的是什么？——结论：因为局部最远可能跳到 nums 很小、后续无力的点；正确贪的是「在当前这一跳覆盖的范围内，选能让下一跳延伸最远的点」，即按「层边界」分批扩展，层数就是最少步数。
  3. #763 为什么「扫到 end 就切」能保证片段数最多？——结论：因为在 i < end 时切，会让某个已出现字符在后续片段重复出现（违约）；在 i == end 时切，当前片段内所有字符都不再出现，此时立即闭合能给后续片段留最多切分机会，符合「尽可能多」。
Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
LeetCode Hot 100——动态规划篇（状态定义、转移方程、背包）
Next Post
LeetCode Hot 100——堆篇（TopK、频率统计、数据流中位数）