贪心：任务调度与区间综合题

加油站（LeetCode 134）

一圈 n 个加油站，起点 i 加 gas[i] 升油，到下一站消耗 cost[i] 升，求能跑完全圈的起点（不存在返回-1）。

贪心思路

核心观察：从 A 出发，累计油量在 B 处第一次降到负数，那么 A 到 B 之间的任何站都不能作为起点（否则会在 B 更早出现负数），直接跳到 B+1 作为新候选起点。

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

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

模拟过程（gas=[1,2,3,4,5], cost=[3,4,5,1,2]）：

i=0：cur=1-3=-2 < 0 → start=1, cur=0
i=1：cur=2-4=-2 < 0 → start=2, cur=0
i=2：cur=3-5=-2 < 0 → start=3, cur=0
i=3：cur=4-1=3
i=4：cur=3+(5-2)=6

total=(1+2+3+4+5)-(3+4+5+1+2)=0 ≥ 0 → 答案是 start=3 ✓

时间 O(n)，空间 O(1)。

分发糖果（LeetCode 135）

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

两次扫描

一次遍历无法同时满足两侧约束，分两步各保证一侧：

int candy(int[] ratings) {
    int n = ratings.length;
    int[] candy = new int[n];
    Arrays.fill(candy, 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);

    return Arrays.stream(candy).sum();
}

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

初始：[1,1,1,1,1,1,1]

左→右（递增就加1）：
1<2<87：candy→[1,2,3,1,1,1,1]（87=87不变）

右→左（递减就加1取最大）：
87>2>1：从右到左 → [1,2,3,1,3,2,1]

总：13 ✓

用最少箭刺破气球（LeetCode 452）

坐标轴上 n 个气球用区间 [start, end] 表示，一支箭射穿所有覆盖该位置的气球，求最少箭数。

贪心：按右端点排序

把箭射在每批重叠气球最右侧的那个气球右端点处，效益最大（最多射穿气球，且对后续气球留最大余地）。

int findMinArrowShots(int[][] points) {
    // 按右端点排序
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    
    int arrows = 1;
    int shotAt = points[0][1];  // 第一支箭的位置

    for (int[] p : points) {
        if (p[0] > shotAt) {    // 当前气球在箭的右边→需新箭
            arrows++;
            shotAt = p[1];
        }
        // 否则当前箭能射中（p[0] <= shotAt <= p[1]）
    }
    return arrows;
}

划分字母区间（LeetCode 763）

将字符串划分为尽量多的片段，使得每个字母只出现在一个片段中，返回各段长度。

贪心：跟踪每个字母最后出现位置

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> res = 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) {               // 到达右边界，切割
            res.add(end - start + 1);
            start = end + 1;
        }
    }
    return res;
}

模拟过程（s = "ababcbacadefegdehijhklij"）：

各字母最后出现位置：
a→8, b→5, c→7, d→14, e→15, f→11, g→13, h→19, i→22, j→23, k→20, l→21

扫描：
i=0(a): end=max(0,8)=8
i=1(b): end=max(8,5)=8
...
i=8(a): end=8, i==end → 片段1=[0,8], 长度9, start=9

i=9(d): end=14
i=10(e): end=15
... 
i=15(e): end=15, i==end → 片段2=[9,15], 长度7, start=16

i=16(i): end=22
...
i=23(j): end=23, i==end → 片段3=[16,23], 长度8

结果：[9,7,8] ✓

坐船问题（LeetCode 881）

每艘船承重 limit，每次最多载 2 人，体重为 people[i]，求最少船数。

贪心：双指针配对

重的人和轻的人配对——最重的人和最轻的人尝试同船，能载则一起，否则重的人单独一艘。

int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int lo = 0, hi = people.length - 1, boats = 0;

    while (lo <= hi) {
        if (people[lo] + people[hi] <= limit) lo++;  // 最轻的能和最重的同船
        hi--;   // 最重的总要坐一艘船
        boats++;
    }
    return boats;
}

为什么正确：最重的人一定要占一艘船。如果最重的人能和最轻的人同船（限制内），那这是最优配对（轻的人和任何人配对都不比和最轻的人配对差）；否则最重的人单独一艘。

总结