贪心高频变体：跳跃、分配与调度

跳跃游戏系列

跳跃游戏是贪心的经典题系，考查"覆盖范围"的动态维护。

跳跃游戏 I：能否到达终点？（LeetCode 55）

每个位置的值表示能跳的最大步数，问能否从 0 出发到达最后一个位置。

贪心思路：维护当前能到达的最远下标 maxReach，一旦 i > maxReach 说明当前位置根本到不了，直接返回 false。

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]);  // 更新最远能到的地方
    }
    return true;    // 能走到末尾说明可达
}

模拟过程（nums = [2,3,1,1,4]）：

i=0：maxReach = max(0, 0+2) = 2
i=1：maxReach = max(2, 1+3) = 4  ← 直接能到末尾
i=2：maxReach = max(4, 2+1) = 4
...
结果：true ✓

失败案例（nums = [3,2,1,0,4]）：

i=0：maxReach = 3
i=1：maxReach = 3
i=2：maxReach = 3
i=3：maxReach = 3
i=4：4 > 3 → return false ✓

跳跃游戏 II：最少跳几步？（LeetCode 45）

保证一定能到达，求最少跳跃次数。

贪心思路：不到边界不跳——当走到当前跳能到的最远边界时，才必须跳一次，并更新边界为下一跳能到的最远处。

int jump(int[] nums) {
    int jumps = 0;      // 跳跃次数
    int curEnd = 0;     // 当前跳能到达的最远位置（边界）
    int farthest = 0;   // 下一跳能到的最远位置
    
    // 不需要枚举最后一个位置（到达边界才跳，到末尾就停）
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {     // 到了当前跳的边界，必须起跳
            jumps++;
            curEnd = farthest;  // 边界推进
        }
    }
    return jumps;
}

模拟过程（nums = [2,3,1,1,4]）：

初始：curEnd=0, farthest=0, jumps=0

i=0：farthest=max(0,0+2)=2; i==curEnd → jumps=1, curEnd=2
i=1：farthest=max(2,1+3)=4; i!=curEnd
i=2：farthest=max(4,2+1)=4; i==curEnd → jumps=2, curEnd=4
i=3：farthest=max(4,3+1)=4; i!=curEnd（3≠4）

结果：2 次跳跃 ✓

为什么贪心有效：边界处跳一次，等价于将跳跃分组——每次"跳"是从当前范围跳到能覆盖最远的那次，这就是局部最优（覆盖最远）= 全局最优（最少跳数）。

分发糖果（LeetCode 135）

n 个孩子站成一排，评分更高的孩子必须比相邻孩子得到更多糖果（每人至少 1 颗），求最少总糖果数。

贪心策略：分两步处理两个方向的约束：

1. 左→右：如果 ratings[i] > ratings[i-1]，则 candy[i] = candy[i-1] + 1
2. 右→左：如果 ratings[i] > ratings[i+1]，则 candy[i] = max(candy[i], candy[i+1] + 1)

为什么分两次？一次遍历无法同时满足两侧约束。两次遍历各自保证一侧约束后，取最大值即可同时满足。

int candy(int[] ratings) {
    int n = ratings.length;
    int[] candy = new int[n];
    Arrays.fill(candy, 1);   // 每人至少 1 颗

    // 第一步：从左到右，满足"右比左高则多一颗"
    for (int i = 1; i < n; i++)
        if (ratings[i] > ratings[i - 1])
            candy[i] = candy[i - 1] + 1;

    // 第二步：从右到左，满足"左比右高则多一颗"（取两次的最大值）
    for (int i = n - 2; i >= 0; i--)
        if (ratings[i] > ratings[i + 1])
            candy[i] = Math.max(candy[i], candy[i + 1] + 1);

    int sum = 0;
    for (int c : candy) sum += c;
    return sum;
}

模拟过程（ratings = [1,0,2]）：

初始：[1,1,1]

左→右：
  i=1：0 < 1，不满足，candy[1]=1
  i=2：2 > 0，candy[2]=candy[1]+1=2
→ [1,1,2]

右→左：
  i=1：0 < 2，不满足
  i=0：1 > 0，candy[0]=max(1,candy[1]+1)=max(1,2)=2
→ [2,1,2]

总糖果数：5 ✓

加油站（LeetCode 134）

一圈加油站，从 gas[i] 获得汽油，行驶到下一站消耗 cost[i]，找出能完成一圈的起始位置（返回-1则不存在）。

关键观察：

1. 若 sum(gas) < sum(cost)，全程油不够，必然返回 -1
2. 若油够，贪心策略：从候选起点出发，油量一旦为负数（cur < 0），说明从上一次重置的起点到当前位置，中间任何一站都不行，将起点重置为下一站

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0;   // 总油量差（判断是否有解）
    int cur = 0;     // 当前从 start 出发的累计油量
    int start = 0;   // 候选起点

    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        cur += diff;
        if (cur < 0) {          // 从 start 到 i 油不够
            start = i + 1;      // 重置起点
            cur = 0;
        }
    }
    return total >= 0 ? start : -1;
}

为什么贪心有效：若从 A 出发，到 B 时油量为负，则从 A 到 B 之间任意点出发都会在 B 处或之前耗尽（因为 A 到 B 累计差为负数）。所以直接跳到 B+1 作为下一候选起点。

任务调度器（LeetCode 621）

CPU 执行 tasks，相同任务间隔不能少于 n 轮（冷却），求最少总执行时间。

贪心数学分析：

• 设最高频任务出现 maxFreq 次，有 maxCount 种任务同样频率
• 框架：(maxFreq - 1) 个完整冷却块 × (n+1) 时间槽 + 最后一批 maxCount 任务
• 若任务总数 > 框架，框架不是瓶颈，直接用 tasks.length

例：tasks = [A,A,A,B,B,B,C], n=2
maxFreq=3(A,B), maxCount=2

框架：_ _ _ | _ _ _ | A B
槽：  A B C | A B C | A B
时间：(3-1)*(2+1) + 2 = 8

即  A B C A B C A B  → 8个时间单位 ✓

int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char c : tasks) freq[c - 'A']++;
    Arrays.sort(freq);                 // 升序，末尾是最高频

    int maxFreq = freq[25];
    int maxCount = 0;
    for (int f : freq) if (f == maxFreq) maxCount++;

    // 框架大小 vs 任务总数，取更大的
    return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
}

总结