在算法的世界里，有一种思想既简单又复杂，既高效又危险，它就是——贪心算法。

很多人在初次接触贪心算法时，都会陷入一个误区：认为“每一步都选最好的，结果一定是最好的”。但现实往往是残酷的，贪心算法并不总是能得出全局最优解。那么，它到底在什么情况下是“神兵利器”，什么情况下又会变成“陷阱”呢？

今天，我们不谈枯燥的理论，直接通过两个力扣（LeetCode）上的经典题目——最大交换和分发糖果，来把贪心算法的“脾气”和“套路”摸个透。

一、什么是贪心算法？先理解它的“三宗最”

在开始案例之前，我们先给贪心算法画个像。它是一种在每一步选择中都采取当前状态下最优的策略，也就是我们常说的“局部最优解”，并期望通过累积这些局部最优解，最终达到“全局最优解”。

它有三大鲜明的特点：

1. 选择性：每一步，都有一个明确的“贪心策略”告诉你该选哪个。

2. 不可回溯：一旦做了选择，就没有“后悔药”，不能回头重新考虑。

3. 局部最优：它只看眼前，不看长远。

那么，什么样的场景下贪心算法能“得逞”呢？需要满足两个苛刻的条件：

• 贪心选择性质：局部最优的选择，最终能导向全局最优解。

• 最优子结构：一个问题的最优解，包含了其子问题的最优解。

听起来有点抽象？没关系，我们进入实战。

二、案例一：最大交换（LeetCode 670）

题目：给你一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例：输入 2736，输出 7236（交换数字2和7）。

这道题是贪心算法的入门级应用题，完美诠释了“如何做出一次最正确的选择”。

1. 思路剖析：贪心策略如何定？

直觉告诉我们，为了得到最大值，我们应该尽量把高位的数字变大。比如在 2736 中，最高位是千位的“2”，我们希望能把它换成后面数字中最大的那个。

但这里有个陷阱：如果后面最大的数字不止一个，我们该换哪个？例如 1993，最高位是“1”，后面最大的数字是“9”，我们应该交换最高位的“1”和最后出现的那个“9”，得到 9193 吗？不，我们应该得到 9193 还是 9913？

其实，正确的贪心策略是：从右向左遍历，维护一个“最大数字的索引”。一旦遇到一个数字比它右边某个最大值小，就准备交换。

更通俗的解法是：

1. 将数字转化为字符数组，方便操作。

2. 核心逻辑：从右向左扫描，记录当前遍历过的数字中，最大数字的索引。

3. 贪心决策：如果当前数字 num_list[i] 小于我们记录的 max_index 指向的数字，那么交换 i 和 max_index 这两个位置，就能让当前位的数字变大，从而得到更大的数。

4. 因为我们要找的是“第一个”能使数字变大的交换机会，所以一旦找到，立即交换并返回结果。

2. 代码实现与解读

下面是一段经典的实现代码，我们来逐行拆解：

python

def maximumSwap(num):
    # 将数字转成列表，方便操作每一位
    s = list(str(num))
    n = len(s)
    
    # 记录从当前位置开始，右侧最大数字的索引
    max_idx = n - 1
    # 记录要进行交换的左边位置和右边位置
    left, right = -1, -1
    
    # 从右向左遍历，这是贪心算法的关键
    for i in range(n - 1, -1, -1):
        # 如果当前数字比“右侧最大值”大，更新右侧最大值的索引
        if s[i] > s[max_idx]:
            max_idx = i
        # 如果当前数字比“右侧最大值”小，这是一个潜在的交换点
        elif s[i] < s[max_idx]:
            # 记录下要交换的左边位置和右边位置
            left, right = i, max_idx
    
    # 如果没有找到需要交换的位置，说明数字本身已经是最大值
    if left == -1:
        return num
    
    # 执行交换
    s[left], s[right] = s[right], s[left]
    return int(''.join(s))

为什么这是贪心？
因为在每一步，我们都只关心“当前这个位置，是否应该与它右边最大的那个数字交换”。我们并没有去考虑交换之后，后面的数字会如何排列。这正是贪心算法的精髓——用局部的最优选择（交换后当前位变大），去实现全局的最优（整个数字最大）。

三、案例二：分发糖果（LeetCode 135）

如果说“最大交换”是贪心算法的开胃菜，那“分发糖果”就是一道硬菜。它要求我们同时考虑两个方向的约束条件，是贪心算法“两次遍历”思想的经典应用。

题目：n 个孩子站成一排，每个孩子有一个评分 ratings。你需要给孩子们发糖果，要求：

1. 每个孩子至少 1 个糖果。

2. 相邻的两个孩子中，评分更高的孩子必须获得更多的糖果。

请计算并返回最少需要准备的糖果数目。

1. 方法一：两次遍历（最直观的贪心）

这是最容易理解的方法，它通过两次贪心遍历，分别满足“左邻右舍”的规则。

思路：

1. 初始化：每个孩子先发 1 个糖果。

2. 第一次遍历（从左到右）：如果右边的孩子评分比左边高，那么右边孩子的糖果数至少是左边孩子糖果数 + 1。这是一个贪心策略：为了满足“右边 > 左边”的关系，我们只给右边增加最少的必要糖果。

3. 第二次遍历（从右到左）：如果左边的孩子评分比右边高，那么左边孩子的糖果数至少是右边孩子糖果数 + 1。注意，这里要取一个 max 值，因为左边孩子可能已经在第一次遍历中被分配了糖果，我们不能让它减少，只能取两者中的较大值，以同时满足两边的规则。

代码实现：

python

def candy(ratings):
    n = len(ratings)
    # 初始化每个孩子至少1个糖果
    candies = [1] * n
    
    # 从左向右遍历：满足右边孩子比左边孩子评分高的规则
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    
    # 从右向左遍历：满足左边孩子比右边孩子评分高的规则，同时取最大值
    total = candies[-1]
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
        total += candies[i]
    
    return total

贪心思想体现：
这里我们用了两次贪心。第一次贪心解决了“向右看”的问题，第二次贪心解决了“向左看”的问题。这种“分而治之”的思路，正是贪心算法灵活性的体现。

2. 方法二：一次遍历（波峰波谷法）

如果你觉得两次遍历还不够过瘾，那么这种方法将展示贪心算法的极致优雅——一次遍历，通过维护“上升区”和“下降区”的长度来计算糖果总数。

思路：
我们把整个评分数组看作一个折线图，可以分为三种区域：

• 上升区：ratings[i] > ratings[i-1]

• 下降区：ratings[i] < ratings[i-1]

• 平缓区：ratings[i] == ratings[i-1]

核心逻辑是：

• 上升区：糖果数递增，每增加一个上升，就在结果中累加一个递增的值。

• 下降区：糖果数递减，但这里有一个难点——峰值（上升区的终点）的糖果数，需要同时满足上升区和下降区的要求。因此，当下降区的长度最终等于上升区的长度时，峰值位置需要额外多分一个糖果。

代码实现与深度解读：

python

def candy(ratings):
    n = len(ratings)
    # 每个孩子至少一个糖果，先给结果加上基础值
    result = n
    
    up_length = 0      # 当前上升区的长度
    down_length = 0    # 当前下降区的长度
    up_num = 0         # 记录上一个上升区的长度，用于峰值比较
    
    for i in range(1, n):
        # 1. 处于上升区
        if ratings[i] > ratings[i-1]:
            up_length += 1      # 上升区长度增加
            down_length = 0     # 下降区清零
            up_num = up_length  # 记录当前上升区的长度，供后续下降区使用
            result += up_length # 累加糖果数，上升区每增加1，就多分一个糖果
        
        # 2. 处于下降区
        elif ratings[i] < ratings[i-1]:
            # 关键逻辑：判断峰值的归属
            # 如果上升区长度为0，说明现在就是纯下降区，下降区长度正常+1
            if up_length == 0:
                down_length += 1
            # 如果下降区长度已经等于之前的上升区长度，意味着峰值需要“让位”
            # 此时准下降区转变为真下降区，下降区长度+1，同时峰值在下降区也算一次
            if down_length == up_num:
                down_length += 1
            
            up_length = 0       # 清空上升区
            result += down_length # 累加糖果数
            
        # 3. 处于平缓区
        else:
            # 清空所有记录，一切重新开始
            up_length = 0
            down_length = 0
            up_num = 0
    
    return result

为什么这个“准下降区”的概念如此重要？
考虑一个场景：评分 [1, 2, 3, 2, 1]。糖果分配应该是 [1, 2, 3, 2, 1]，总数是 9。

• 上升区：1,2,3，长度 up_length=2（从第2个到第3个）。

• 下降区：3,2,1，长度 down_length=2（从第4个到第5个）。

• 峰值：位置3（数值3）的糖果数由上升区决定，为3个。

• 如果我们不处理“准下降区”的边界问题，下降区可能会错误地多算或漏算峰值位置的糖果。

这个算法通过 up_num 记住上升区的长度，并在下降区长度追上它时，通过 down_length += 1 来补偿峰值那一个糖果，保证了结果的正确性。这是一次非常精妙的贪心优化。

四、总结：贪心算法的“使用说明书”

看完这两个案例，相信你对贪心算法已经有了更立体的认识。

1. 贪心不是万能药，但用对了是神药：

   • 当问题具有贪心选择性质和最优子结构时，贪心算法能给出简洁高效的解。

   • “最大交换”利用了“高位换大数”的贪心，直接得到最优解。

   • “分发糖果”则通过两次遍历，分别解决了单向约束，最终满足全局条件。

2. 贪心的核心在于“策略”：

   • 第一步永远是分析问题，找到那个“局部最优”的决策标准。

   • 这个标准必须清晰、可操作，并且不依赖于未来的状态（不可回溯）。

3. 贪心的进阶：处理复杂约束：

   • 当问题涉及双向约束时（如“分发糖果”），我们可以通过多次贪心（如两次遍历）或维护状态变量（如波峰波谷法）来优雅地解决。

4. 如何判断是否能用贪心？

   • 当你发现一个问题可以通过一个简单的规则，在不影响后续决策的情况下，一步步构建出解时，可以考虑贪心。

   • 如果存在一个“反例”能证明局部最优不能导向全局最优，那么贪心算法就不适用，可能需要考虑动态规划。

最后，回到我们开头的问题：贪心算法，到底是天使还是魔鬼？它其实是一把锋利的刀。用好了，可以削铁如泥；用错了，可能会误伤自己。关键在于，你是否真正理解了问题的结构，以及你手中的这把“贪心刀”，是否恰好能切开问题的核心。

希望今天的分享能帮你打开贪心算法的大门。如果你觉得有收获，不妨去力扣上亲手敲一敲这两道题，感受一下贪心算法的魅力。