Day 21 - 贪心

📅 日期：2026年3月8日 🎯 主题：贪心算法基础 - 局部最优与全局最优

今日题目

题目1：分发饼干 (Assign Cookies)

难度：⭐ 简单

链接：LeetCode 455. 分发饼干

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例：

输入：g = [1,2,3], s = [1,1]
输出：1
解释：你有三个孩子和两块小饼干，3 个孩子的胃口值分别是 1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。

输入：g = [1,2], s = [1,2,3]
输出：2
解释：你有两个孩子和三块小饼干，两个孩子的胃口值分别是 1,2。
拥有的饼干数量和尺寸都足以让所有孩子满足，所以输出 2。

提示：

• 1 <= g.length <= 3 * 10^4
• 0 <= s.length <= 3 * 10^4
• 1 <= g[i], s[j] <= 2^31 - 1

解题思路

方法一：贪心 + 双指针

核心思想：

1. 将孩子胃口和饼干尺寸都排序
2. 用最小的饼干满足最小胃口的孩子（或用刚好能满足的最小饼干）
3. 如果当前饼干能满足当前孩子，计数+1，双指针都后移；否则饼干指针后移

贪心策略：小饼干优先满足小胃口的孩子，避免大饼干浪费在小胃口上

代码实现

import java.util.*;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int child = 0, cookie = 0;
        while (child < g.length && cookie < s.length) {
            if (s[cookie] >= g[child]) {
                // 当前饼干能满足当前孩子
                child++;
            }
            // 无论是否满足，饼干都要用掉（或太小不满足也要跳过）
            cookie++;
        }
        return child;
    }
}

复杂度分析

• 时间复杂度：O(n log n + m log m)，排序为主
• 空间复杂度：O(1)

---

题目2：跳跃游戏 (Jump Game)

难度：⭐⭐ 中等

链接：LeetCode 55. 跳跃游戏

题目描述

给你一个非负整数数组 nums，你最初位于数组的 第一个下标。数组中的每个元素代表你在该位置可以跳跃的 最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。

示例：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1，然后再从下标 1 跳 3 步到达最后一个下标。

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标 3 处。但该下标的最大跳跃长度是 0，所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

解题思路

方法一：贪心 - 维护最远可达位置

核心思想：

1. 不需要模拟每一步跳跃，只需要维护「当前能到达的最远位置」
2. 遍历数组，如果当前位置超过最远可达位置，说明无法到达
3. 否则更新最远可达位置：maxReach = max(maxReach, i + nums[i])
4. 如果最远可达位置 >= 最后下标，返回 true

贪心策略：每一步都尽可能扩展能到达的最远范围

代码实现

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // 如果当前位置超过了之前能到达的最远位置，说明断开了
            if (i > maxReach) {
                return false;
            }
            // 更新最远可达位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 提前终止
            if (maxReach >= n - 1) {
                return true;
            }
        }
        return true;
    }
}

方法二：从后往前贪心

从终点往前看，维护「能到达终点的最小位置」。

class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;

        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

复杂度分析

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

---

今日总结

学到了什么？

1. 贪心本质：每一步选择局部最优，期望达到全局最优
2. 分发饼干：排序 + 双指针，小饼干优先满足小胃口
3. 跳跃游戏：维护最远可达位置，不需要模拟具体跳跃过程

贪心 vs 动态规划

特点	贪心	动态规划
决策	每步选局部最优	考虑所有可能
回溯	不回退	可能需要回溯
复杂度	通常更低	通常更高
适用条件	最优子结构 + 贪心选择性质	最优子结构 + 重叠子问题

贪心解题思路

1. 找贪心策略：每一步如何选择局部最优？
2. 证明正确性：局部最优能否推出全局最优？（考试需要，刷题可凭直觉）
3. 实现：通常配合排序、双指针、优先队列等

相似题目推荐

• 跳跃游戏 II - 求最少跳跃次数
• 加油站 - 环形路线贪心
• 分发糖果 - 双向遍历贪心
• 用最少数量的箭引爆气球 - 区间贪心

明日计划

• Day 22 贪心进阶
• 练习：跳跃游戏 II、加油站等