深度拆解贪心算法：从“局部最优”到“全局最优”，看完这两个案例你就懂了
在算法的世界里，有一种思想既简单又复杂，既高效又危险，它就是——贪心算法。
很多人在初次接触贪心算法时，都会陷入一个误区：认为“每一步都选最好的，结果一定是最好的”。但现实往往是残酷的，贪心算法并不总是能得出全局最优解。那么，它到底在什么情况下是“神兵利器”，什么情况下又会变成“陷阱”呢？
今天，我们不谈枯燥的理论，直接通过两个力扣（LeetCode）上的经典题目——最大交换和分发糖果，来把贪心算法的“脾气”和“套路”摸个透。
一、什么是贪心算法？先理解它的“三宗最”
在开始案例之前，我们先给贪心算法画个像。它是一种在每一步选择中都采取当前状态下最优的策略，也就是我们常说的“局部最优解”，并期望通过累积这些局部最优解，最终达到“全局最优解”。
它有三大鲜明的特点：
选择性：每一步，都有一个明确的“贪心策略”告诉你该选哪个。
不可回溯：一旦做了选择，就没有“后悔药”，不能回头重新考虑。
局部最优：它只看眼前，不看长远。
那么，什么样的场景下贪心算法能“得逞”呢？需要满足两个苛刻的条件：
贪心选择性质：局部最优的选择，最终能导向全局最优解。
最优子结构：一个问题的最优解，包含了其子问题的最优解。
听起来有点抽象？没关系，我们进入实战。
二、案例一：最大交换（LeetCode 670）
题目：给你一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例：输入2736，输出7236（交换数字2和7）。
这道题是贪心算法的入门级应用题，完美诠释了“如何做出一次最正确的选择”。
1. 思路剖析：贪心策略如何定？
直觉告诉我们，为了得到最大值，我们应该尽量把高位的数字变大。比如在2736中，最高位是千位的“2”，我们希望能把它换成后面数字中最大的那个。
但这里有个陷阱：如果后面最大的数字不止一个，我们该换哪个？例如1993，最高位是“1”，后面最大的数字是“9”，我们应该交换最高位的“1”和最后出现的那个“9”，得到9193吗？不，我们应该得到9193还是9913？
其实，正确的贪心策略是：从右向左遍历，维护一个“最大数字的索引”。一旦遇到一个数字比它右边某个最大值小，就准备交换。
更通俗的解法是：
将数字转化为字符数组，方便操作。
核心逻辑：从右向左扫描，记录当前遍历过的数字中，最大数字的索引。
贪心决策：如果当前数字
num_list[i]小于我们记录的max_index指向的数字，那么交换i和max_index这两个位置，就能让当前位的数字变大，从而得到更大的数。因为我们要找的是“第一个”能使数字变大的交换机会，所以一旦找到，立即交换并返回结果。
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. 方法一：两次遍历（最直观的贪心）
这是最容易理解的方法，它通过两次贪心遍历，分别满足“左邻右舍”的规则。
思路：
初始化：每个孩子先发 1 个糖果。
第一次遍历（从左到右）：如果右边的孩子评分比左边高，那么右边孩子的糖果数至少是左边孩子糖果数 + 1。这是一个贪心策略：为了满足“右边 > 左边”的关系，我们只给右边增加最少的必要糖果。
第二次遍历（从右到左）：如果左边的孩子评分比右边高，那么左边孩子的糖果数至少是右边孩子糖果数 + 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来补偿峰值那一个糖果，保证了结果的正确性。这是一次非常精妙的贪心优化。
四、总结：贪心算法的“使用说明书”
看完这两个案例，相信你对贪心算法已经有了更立体的认识。
贪心不是万能药，但用对了是神药：
当问题具有贪心选择性质和最优子结构时，贪心算法能给出简洁高效的解。
“最大交换”利用了“高位换大数”的贪心，直接得到最优解。
“分发糖果”则通过两次遍历，分别解决了单向约束，最终满足全局条件。
贪心的核心在于“策略”：
第一步永远是分析问题，找到那个“局部最优”的决策标准。
这个标准必须清晰、可操作，并且不依赖于未来的状态（不可回溯）。
贪心的进阶：处理复杂约束：
当问题涉及双向约束时（如“分发糖果”），我们可以通过多次贪心（如两次遍历）或维护状态变量（如波峰波谷法）来优雅地解决。
如何判断是否能用贪心？
当你发现一个问题可以通过一个简单的规则，在不影响后续决策的情况下，一步步构建出解时，可以考虑贪心。
如果存在一个“反例”能证明局部最优不能导向全局最优，那么贪心算法就不适用，可能需要考虑动态规划。
最后，回到我们开头的问题：贪心算法，到底是天使还是魔鬼？它其实是一把锋利的刀。用好了，可以削铁如泥；用错了，可能会误伤自己。关键在于，你是否真正理解了问题的结构，以及你手中的这把“贪心刀”，是否恰好能切开问题的核心。
希望今天的分享能帮你打开贪心算法的大门。如果你觉得有收获，不妨去力扣上亲手敲一敲这两道题，感受一下贪心算法的魅力。