贪心综合：数组调整与特殊问题

不等式数组问题：摆动序列（LeetCode 376）

求数组的最长摆动子序列长度（相邻元素大小交替变化）。

贪心策略：贪心地保留每个"转折点"。遍历时只要连续方向相同就跳过，一旦方向改变就计数。

int wiggleMaxLength(int[] nums) {
    if (nums.length < 2) return nums.length;
    
    int len = 1;  // 至少有1个元素
    String dir = "";  // 当前方向
    
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1] && !dir.equals("up")) {
            len++;
            dir = "up";
        } else if (nums[i] < nums[i - 1] && !dir.equals("down")) {
            len++;
            dir = "down";
        }
    }
    return len;
}

// 更简洁的写法
int wiggleMaxLength2(int[] nums) {
    int up = 1, down = 1;   // 以上升/下降结尾的最长摆动子序列
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) up = down + 1;
        else if (nums[i] < nums[i - 1]) down = up + 1;
    }
    return Math.max(up, down);
}

模拟过程（nums = [1,7,4,9,2,5]）：

初始：up=1, down=1

i=1: 7>1 → up=down+1=2
i=2: 4<7 → down=up+1=3
i=3: 9>4 → up=down+1=4
i=4: 2<9 → down=up+1=5
i=5: 5>2 → up=down+1=6

结果：max(6,5)=6 ✓（整个数组就是摆动序列）

区间覆盖：用最少线段覆盖区间（LeetCode 1024）

有若干视频片段 clips[i]=[start,end]，求最少多少个片段能拼接成 [0, time] 的完整视频。

贪心策略：

1. 按左端点排序
2. 在当前已覆盖范围内，贪心选择右端延伸最长的片段
3. 当必须切换片段时才计数

int videoStitching(int[][] clips, int time) {
    // 按左端点排序，左端点相同则右端点大的优先
    Arrays.sort(clips, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
    
    int count = 0;      // 选用的片段数
    int curEnd = 0;     // 当前已覆盖的右边界
    int farthest = 0;   // 下一段能到的最远位置
    int i = 0;
    int n = clips.length;
    
    while (curEnd < time) {
        // 在左端 <= curEnd 的所有片段中选右端最大的
        while (i < n && clips[i][0] <= curEnd) {
            farthest = Math.max(farthest, clips[i][1]);
            i++;
        }
        
        if (farthest <= curEnd) return -1;  // 无法继续延伸
        
        count++;
        curEnd = farthest;  // 推进覆盖范围
    }
    return count;
}

模拟过程（clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time=10）：

排序后（按左端点）：
[0,2][1,5][1,9][4,6][5,9][8,10]

curEnd=0, farthest=0, count=0

轮次1：左端<=0的片段：[0,2] → farthest=2
        farthest=2>0 → count=1, curEnd=2

轮次2：左端<=2的片段：[1,5][1,9] → farthest=9
        farthest=9>2 → count=2, curEnd=9

轮次3：左端<=9的片段：[4,6][5,9][8,10] → farthest=10
        farthest=10>9 → count=3, curEnd=10

curEnd=time → 返回 3 ✓

种花问题（LeetCode 605）

花坛中已种一些花（1），空位（0）。不能相邻种花，判断能否再种入 n 株。

贪心：从左到右扫描，看到空位且两侧（或边界）也为空时，立刻种花（贪心地早种）。

boolean canPlaceFlowers(int[] flowerbed, int n) {
    int count = 0;
    for (int i = 0; i < flowerbed.length; i++) {
        if (flowerbed[i] == 0) {
            boolean leftEmpty = (i == 0 || flowerbed[i - 1] == 0);
            boolean rightEmpty = (i == flowerbed.length - 1 || flowerbed[i + 1] == 0);
            if (leftEmpty && rightEmpty) {
                flowerbed[i] = 1;  // 种花（修改原数组确保后续不重复种）
                count++;
            }
        }
    }
    return count >= n;
}

为什么贪心有效：尽早种花不会阻止本来能种的位置（每次种花之间至少间隔一个空位，不影响更右侧的空位判断）。

分隔字母区间（LeetCode 763）

尽可能多地给字符串分段，每段内每种字母只出现在该段中，不跨段。

贪心：

1. 预先记录每种字母最后出现的下标
2. 扫描时动态更新当前段的右边界（滑动右端点）
3. 当前下标恰好等于右边界时，一段结束

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;
}

最优账单平衡（LeetCode 465，Hard）

一组人之间有若干借贷记录，求最少交易次数结清所有债务。

贪心/回溯：

1. 计算每个人的净余额（正数=债主，负数=欠债）
2. 用 DFS/贪心匹配：用正余额偿还负余额，正负配对

int minTransfers(int[][] transactions) {
    Map<Integer, Integer> balance = new HashMap<>();
    for (int[] t : transactions) {
        balance.merge(t[0], -t[2], Integer::sum);  // 出钱方
        balance.merge(t[1], t[2], Integer::sum);   // 收钱方
    }
    
    // 去掉余额为0的人
    List<Integer> debts = new ArrayList<>();
    for (int v : balance.values())
        if (v != 0) debts.add(v);
    
    return dfs(debts, 0);
}

int dfs(List<Integer> debts, int start) {
    while (start < debts.size() && debts.get(start) == 0) start++;
    if (start == debts.size()) return 0;
    
    int res = Integer.MAX_VALUE;
    for (int i = start + 1; i < debts.size(); i++) {
        // 只有符号相反的才值得配对（一个欠债一个是债主）
        if (debts.get(i) * debts.get(start) < 0) {
            debts.set(i, debts.get(i) + debts.get(start));  // 合并
            res = Math.min(res, 1 + dfs(debts, start + 1));
            debts.set(i, debts.get(i) - debts.get(start));  // 回溯
        }
    }
    return res;
}

总结

贪心的本质：在约束条件下，每一步的最优局部选择能积累到全局最优——关键是找到"不后悔"的贪心策略，即当前选择不会让后续变差。