贪心算法：简单又强大的“当下最优”决策艺术

在算法世界里，贪心算法就像一个“购物节只加购当前最划算商品”的消费者——它不从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优解。它只着眼于当前步骤的最佳选择，希望以此导致全局最优。相比于动态规划的“全局规划、存储备忘”和回溯法的“深度探索、不行就退”，贪心算法以其思路直接、代码简洁、执行高效的特点，成为解决特定优化问题的“神兵利器”。

一、贪心算法核心解析

1. 核心思想与哲学

贪心算法的本质是：通过一系列局部最优选择，期望达到全局最优。

它采用自顶向下的问题分解方式，将问题划分为一系列连续的决策阶段。在每一个阶段，它都做出一个在当前状态下看起来最好的选择（即局部最优解）。这个选择一旦做出，就不可更改（无后效性），也不会回溯考虑其他可能性。

一个生动的比喻：你在一片玉米地里，只能一直向前走，不能回头。你的目标是摘到最大的玉米。贪心策略就是：每次看到眼前的玉米，都摘下你所能看到的最大的那一个。这不一定能保证你最终得到全地最大的玉米，但在特定条件下（比如玉米大小随位置有某种规律），这可能就是最优策略。

2. 关键性质（如何判断能否用贪心？）

贪心算法不是“万金油”，其正确性严重依赖于问题本身的性质。在尝试使用贪心前，必须验证以下两点：

• 贪心选择性质 (Greedy Choice Property)：

  这是贪心算法的核心特征。指的是一个问题的全局最优解，可以通过一系列局部最优（贪心）的选择来得到。

  • 简单来说：每一步都选当前最好的，凑起来就是全局最好的。
  • 与动态规划的区别：动态规划中，每一步的选择依赖于所有子问题的解，需要“瞻前顾后”。而贪心算法在选择时，只考虑当前状态，不受未来或子问题解的影响。

• 最优子结构 (Optimal Substructure)：

  指的是一个问题的最优解，包含了其子问题的最优解。

  • 注意：这是贪心算法和动态规划算法共有的性质。一个问题具有最优子结构，是它能用优化算法（贪心或DP）解决的前提，但不足以证明贪心有效。必须同时满足“贪心选择性质”，才能用贪心。

3. 做题技巧与常用策略

1. 排序预处理：这是贪心问题中最常见的操作。通过排序（如按开始时间、结束时间、权重、比例等），可以制造出能够进行“贪心选择”的序列。例如，区间问题常按结束时间排序，背包的分数背包问题按价值密度排序。
2. 优先级队列（堆）的运用：当我们需要动态地、重复地获取当前“最优”元素时，堆是贪心算法的绝佳搭档。例如，哈夫曼编码、多次选取当前最大值/最小值的问题。
3. 反证法证明：在面试或笔试中，如果不能一眼看出贪心策略的正确性，可以尝试使用反证法。基本思路：假设存在一个不包含当前贪心选择的最优解，然后通过“交换论证”等方式，将这个最优解修改为包含当前贪心选择的另一个解，并且不会更差，从而证明贪心选择总是安全的。
4. 数学归纳法证明：另一种严谨的证明方法。证明第一步的贪心选择是正确的，然后假设前k步的贪心选择能导向最优解，证明第k+1步的贪心选择也能保持这个性质。

4. 常见应用场景

• 分配问题：如何将有限的资源分配给需求方，以达到最大效益（如分发饼干、任务调度器）。
• 区间问题：涉及线段、时间区间等的选择、覆盖、合并、安排（如无重叠区间、用最少数量的箭引爆气球、合并区间）。
• 路径/成本/构造问题：在图论或构造中寻找最优解（如最小生成树（Prim, Kruskal算法）、最短路径（Dijkstra算法）、哈夫曼编码）。
• 买卖股票的最佳时机系列问题（部分子问题）。
• 加油站问题：判断汽车能否绕环行驶。

二、力扣例题实战

例题1：分发饼干（LeetCode 455）

455. 分发饼干 - 力扣（LeetCode）

题目描述

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

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

贪心策略分析

这是一个典型的**“最大匹配”**贪心问题。核心矛盾在于：一块饼干只能给一个孩子，如何分配才能满足更多孩子？

• 错误策略思考：如果把大饼干先给胃口大的孩子，可能会“浪费”大饼干，导致很多小胃口孩子没有合适的小饼干。
• 正确策略证明：为了满足最多孩子，我们应避免浪费。将孩子和饼干分别按胃口和尺寸升序排序。用小胃口孩子去匹配小饼干，如果当前最小饼干不能满足当前胃口最小的孩子，那么这块饼干也不可能满足后面任何孩子（因为后面孩子胃口更大），可以安全丢弃。这样可以确保每一块饼干都去满足它能满足的、胃口最小的那个孩子，从而为后续的孩子留出更大的饼干。这是一个经典的“贪心选择性质”体现。

题解实现

Java 版本

import java.util.Arrays;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 步骤1：对孩子胃口和饼干尺寸升序排序（贪心策略的前提）
        Arrays.sort(g);
        Arrays.sort(s);
        
        // 步骤2：双指针初始化
        int childIndex = 0; // 指向当前待满足的、胃口最小的孩子
        int cookieIndex = 0; // 指向当前可用的、尺寸最小的饼干
        
        // 步骤3：贪心匹配过程
        while (childIndex < g.length && cookieIndex < s.length) {
            if (s[cookieIndex] >= g[childIndex]) {
                // 当前最小饼干可以满足当前胃口最小的孩子 -> 分配，孩子指针后移
                childIndex++;
            }
            // 无论是否成功分配，饼干指针都后移：
            // 1. 分配成功：饼干被消耗，看下一块。
            // 2. 分配失败：这块饼干连最小胃口孩子都无法满足，是废品，丢弃看下一块。
            cookieIndex++;
        }
        
        // childIndex 既是已满足孩子的数量，也是下一个待满足孩子的索引
        return childIndex;
    }
}

Python 版本

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 步骤1：排序
        g.sort()
        s.sort()
        
        # 步骤2：初始化指针
        child_idx = 0
        cookie_idx = 0
        
        # 步骤3：贪心遍历
        while child_idx < len(g) and cookie_idx < len(s):
            if s[cookie_idx] >= g[child_idx]:
                # 满足当前孩子
                child_idx += 1
            # 当前饼干无论是否被消耗，都要查看下一块
            cookie_idx += 1
        
        return child_idx

代码解释与思考

1. 为什么排序是关键？ 排序让我们可以系统地实施“用小饼干满足小胃口”的策略，将原本杂乱无章的匹配问题，转化为有序的线性扫描问题。
2. 双指针的妙用：childIndex和 cookieIndex分别维护了“待满足最小胃口”和“可用最小饼干”的信息。循环条件确保不会越界访问。
3. 核心逻辑的精炼：if (s[cookie] >= g[child])是决策点。childIndex++是贪心成功的动作。cookieIndex++是必然动作，体现了“每块饼干只尝试一次”的贪心思想。

复杂度分析

• 时间复杂度：O(n log n + m log m)，其中 n 是孩子数量，m 是饼干数量。时间主要消耗在排序上，之后的双指针遍历是 O(n + m)。
• 空间复杂度：O(log n + log m)，主要来自于排序算法本身使用的栈空间（如快速排序）。如果使用堆排序，空间复杂度可为 O(1)。我们通常认为额外空间复杂度是 O(1)。

例题2：跳跃游戏（LeetCode 55）

55. 跳跃游戏 - 力扣（LeetCode）

题目描述

给定一个非负整数数组 nums，你最初位于数组的第一个下标。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

贪心策略分析

这题是**“范围覆盖”类贪心的经典题目。我们不需要知道具体跳到哪里，只需要关心最远能覆盖到哪里**。

• 局部最优：在每一步（当前位置 i），根据 nums[i]更新从当前位置能跳到的最远距离 i + nums[i]。并始终维护一个变量 maxReach，表示从起点[0]开始，经过之前所有位置，能到达的最远下标。
• 全局最优：如果最终 maxReach能够覆盖（大于等于）最后一个下标，则成功。
• 贪心选择性质证明：在任意位置 i，如果我们不选择跳到能使得 i + nums[i]最远的那个下一步，而是跳到一个更近的位置，那么后续能跳到的范围只会更小，不会更大。因此，维护一个全局的 maxReach是到达更远处的最佳保证。

题解实现

Java 版本

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if (n == 1) return true; // 只有一个元素，已经在终点
        
        int maxReach = 0; // 初始化最远可到达位置为0
        
        for (int i = 0; i < n; i++) {
            // 关键判断：如果当前遍历到的下标 i 已经超过了之前能到达的最远位置 maxReach
            // 说明从起点无法走到 i，更无法走到终点了
            if (i > maxReach) {
                return false;
            }
            // 更新从起点到当前位置 i 的这段路上，能到达的最远位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 提前终止：如果最远位置已经能覆盖终点，直接返回成功
            if (maxReach >= n - 1) {
                return true;
            }
        }
        // 循环结束，按逻辑一定会提前返回，此处返回false保底
        return false;
    }
}

Python 版本

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True
        
        max_reach = 0
        for i in range(n):
            # 如果当前位置无法到达，则终点也无法到达
            if i > max_reach:
                return False
            # 更新从起点出发，能到达的最远位置
            max_reach = max(max_reach, i + nums[i])
            # 提前结束判断
            if max_reach >= n - 1:
                return True
        return False

代码解释与思考

1. **if (i > maxReach)的含义**：maxReach表示**从起点开始，能够安全抵达的最远下标**。如果循环到的索引 i已经大于这个值，说明“路径断了”，你不可能走到 i`这个位置，因此也绝不可能走到终点。这是算法正确性的关键判断。
2. 更新 maxReach：在可以到达的位置 i上，我们查看从此处起跳能到达的新边界 i + nums[i]，并和历史上的最远边界 maxReach比较，取最大值。这体现了“站在巨人的肩膀上”的思想，利用了之前每一步的信息。
3. 提前终止优化：一旦发现最远边界已经覆盖终点，可以立即返回成功，无需遍历完整个数组。

复杂度分析

• 时间复杂度：O(n)，只需要一次线性扫描。
• 空间复杂度：O(1)，只使用了几个整型变量。

三、总结与对比

1. 核心要义：贪心算法的核心是通过局部最优决策的串联，希望达到全局最优。其关键在于证明“每一步的局部最优选择能最终导致全局最优解”（贪心选择性质）。

2. 解题步骤：

   a. 问题转换：将原问题分解为一系列连续的决策步骤。

   b. 寻找贪心策略：找出在每一步做出局部最优选择的规则（常通过排序、堆等）。

   c. 证明正确性（非常重要）：通过反证法、数学归纳法或交换论证，证明该策略满足“贪心选择性质”。

   d. 实现算法：通常代码简洁，效率很高。

3. 与动态规划（DP）的对比：

   特性	贪心算法	动态规划
   决策依据	仅根据当前状态做出最优选择，无后效性。	当前决策依赖子问题的解，需要查表。
   问题性质	必须具有贪心选择性质和最优子结构。	只需具有最优子结构，可能具有重叠子问题。
   解空间遍历	通常只有一条路径（贪心路径）。	会考虑（显式或隐式地）大量子问题的解。
   效率	通常时间复杂度更低，常为O(n log n)或O(n)。	通常时间复杂度较高，但能解决更广的问题。
   回溯性	不回溯，决策不可逆。	不直接回溯，但通过状态转移考虑了多种可能。
   典型问题	最小生成树，Dijkstra，哈夫曼编码，部分背包。	0-1背包，最长公共子序列，最短路径（Floyd）。

4. 局限性：贪心算法不能解决所有优化问题。很多问题（如0-1背包问题）用贪心会得到错误答案。当问题不满足贪心选择性质时，必须使用动态规划等其他方法。

最后牢记：贪心算法的威力在于其简洁与高效，但它的“刀锋”很薄——只有在对的问题上使用正确的策略，才能所向披靡。掌握它的秘诀是多练习、多思考策略背后的“为什么”，而不仅仅是记住模板。