Day 22 - 贪心

📅 日期：2026年3月8日 🎯 主题：贪心进阶 - 跳跃游戏 II 与加油站

今日题目

题目1：跳跃游戏 II (Jump Game II)

难度：⭐⭐ 中等

链接：LeetCode 45. 跳跃游戏 II

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处：

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例：

输入：nums = [2,3,1,1,4]
输出：2
解释：跳到最后一个位置的最小跳跃数是 2。
     从下标 0 跳到下标 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

输入：nums = [2,3,0,1,4]
输出：2

提示：

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

解题思路

方法一：贪心 - 维护当前跳跃边界和最远位置

核心思想：

1. 不需要模拟具体跳到哪个位置，而是维护「当前这一步能覆盖的范围」
2. 在当前范围内，不断更新「下一步能到达的最远位置」
3. 当遍历到当前范围的边界时，说明必须跳一步了，更新边界为最远位置

贪心策略：在当前能跳的范围内，尽可能跳到最远的位置

代码实现

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;

        int jumps = 0;        // 跳跃次数
        int currentEnd = 0;   // 当前这一步能到达的边界
        int farthest = 0;     // 在当前范围内能到达的最远位置

        for (int i = 0; i < n - 1; i++) {
            // 更新能到达的最远位置
            farthest = Math.max(farthest, i + nums[i]);

            // 到达当前边界，必须跳一步
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }
        return jumps;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

---

题目2：加油站 (Gas Station)

难度：⭐⭐ 中等

链接：LeetCode 134. 加油站

题目描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。如果存在解，则 保证 它是 唯一 的。

示例：

输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出：3
解释：从 3 号加油站出发，油箱有 4 升汽油。开往 4 号加油站，油箱 4 - 1 + 5 = 8 升。
     开往 0 号加油站，油箱 8 - 2 + 1 = 7 升。开往 1 号加油站，油箱 7 - 3 + 2 = 6 升。
     开往 2 号加油站，油箱 6 - 4 + 3 = 5 升。开往 3 号加油站，油箱 5 - 5 = 0 升。
     正好回到起点，完成一圈。

输入：gas = [2,3,4], cost = [3,4,3]
输出：-1

提示：

• n == gas.length == cost.length
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

解题思路

方法一：贪心 - 一次遍历

核心思想：

1. 如果总油量 < 总消耗，一定无解
2. 如果有解，从哪个点出发？假设从 0 开始，如果到 i 油量变负了，说明 0 到 i 都不能作为起点
3. 因为如果从 0 到 i 中任一点 j 出发，到达 i 时油量会更少（因为从 j 前的站点积累了正油量）
4. 所以从 i+1 重新开始尝试

贪心策略：如果从某个起点出发在 i 处油量不足，那么该起点到 i 之间的所有点都不可能是起点

代码实现

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int totalTank = 0;  // 总油量
        int currentTank = 0; // 当前油量
        int start = 0;      // 起始位置

        for (int i = 0; i < n; i++) {
            int diff = gas[i] - cost[i];
            totalTank += diff;
            currentTank += diff;

            // 当前油量不足以到达 i+1，从 i+1 重新开始
            if (currentTank < 0) {
                start = i + 1;
                currentTank = 0;
            }
        }

        // 总油量 >= 0 说明有解
        return totalTank >= 0 ? start : -1;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

---

今日总结

学到了什么？

1. 跳跃游戏 II：维护「当前边界」和「最远可达」，到达边界时跳跃次数+1
2. 加油站：如果从某点出发油量变负，该点之前都不可能是起点
3. 环形问题：可以用「总油量是否 >= 0」判断是否有解

贪心经典模式

模式	典型题目	核心思想
区间贪心	合并区间、射气球	按端点排序，选最优
最值维护	跳跃游戏	维护最远可达
重置起点	加油站	失败时从下一位置重启
双向遍历	分发糖果	左右各扫一遍

贪心证明技巧

1. 反证法：假设存在更优解，推出矛盾
2. 交换论证：任意解都可以通过交换变成贪心解而不变差
3. 数学归纳：证明局部最优能推出全局最优

相似题目推荐

• 用最少数量的箭引爆气球 - 区间贪心
• 无重叠区间 - 区间调度
• 划分字母区间 - 区间合并
• 根据身高重建队列 - 插入策略

明日计划

• Day 23 动态规划
• 练习：爬楼梯、斐波那契数列等基础 DP