---

贪心算法中“局部最优”范围的确定：以非递减数列问题为例

在贪心算法中，“局部最优”的“局部”范围划分是策略设计的核心。这一范围的选择直接影响算法能否从局部最优推导出全局最优。本文以非递减数列问题为例，结合该问题的特性与反例分析，深入探讨如何确定局部范围的边界，并延伸至一般贪心问题的设计原则。

---

一、问题回顾与局部范围的矛盾

问题场景：

给定数组 nums，允许修改 1 个元素，判断是否能将其变为非递减数列。非递减数列定义为：对所有 i，nums[i] <= nums[i+1]。

初步直觉的局限性：

假设仅考虑相邻两元素（nums[i-1] 和 nums[i]），当发现 nums[i-1] > nums[i] 时，直接修改其中一个元素。例如：

• 修改 nums[i-1] = nums[i]，使其满足递增。

反例暴露问题：
以数组 [3,4,2,3] 为例：

1. 初始数组：[3,4,2,3]。
2. i=2 处发现 4 > 2，修改 4 为 2 → [3,2,2,3]。
3. 新的递减对出现：3 > 2（i=1 处），导致整体仍不合法。

矛盾根源：
仅考虑相邻两元素时，修改可能破坏更早的递增性。因此，必须将局部范围扩展到 包含前序元素的三个元素，以确保修改不会引入新的问题。

---

二、局部范围扩展的必要性

1. 问题的依赖链分析

• 修改的影响：修改 nums[i-1] 或 nums[i] 可能影响 nums[i-2] 与 nums[i-1] 的关系。
• 前序约束的传递性：若 nums[i] 修改后，需确保 nums[i-2] <= nums[i-1]（否则新的递减对出现）。

2. 三元素窗口的引入

当遇到递减对 nums[i-1] > nums[i] 时，需检查 nums[i-2]（若存在）以决定修改策略：

• 若 nums[i] >= nums[i-2]：
  可安全修改 nums[i-1] = nums[i]，因为前序递增性仍然保持。
• 若 nums[i] < nums[i-2]：
  必须修改 nums[i] = nums[i-1]，避免破坏前序关系。

示例推演：
数组 [3,4,2,3] 中，i=2 处 4 > 2：

• nums[i] = 2 < nums[i-2] = 3 → 必须修改 nums[2] = 4 → [3,4,4,3]。
• 后续检查 i=3 处 4 > 3，但已用尽修改次数 → 返回 false。

---

三、如何确定贪心算法的“局部”范围？

1. 关键原则

• 依赖链分析：决策的影响是否涉及更早或更晚的元素？
• 约束传递性：当前决策是否会导致后续不可修复的问题？
• 反例验证：通过极端案例测试局部范围是否足够。

2. 通用方法论

问题类型	局部范围选择依据	示例问题
非递减数列	修改可能破坏前序关系 → 需包含前前元素	本文问题
活动选择问题	只关心当前活动结束时间 → 单元素决策	选择最早结束的活动
背包问题（分数）	单位价值最大化 → 单物品属性	按价值密度贪心
哈夫曼编码	合并最小频率节点 → 两节点组合	构建最优前缀码

---

四、发散思考：局部范围的动态调整

1. 动态规划与贪心的对比

• 贪心算法：局部范围固定，依赖当前最优决策。
• 动态规划：局部范围覆盖所有可能状态，通过状态转移保证全局最优。

2. 贪心策略的适用范围

• 最优子结构：问题的最优解包含子问题的最优解。
• 无后效性：当前决策不影响后续子问题的结构。

3. 贪心失败的反例

若局部范围过小，可能导致后续无法修复的错误。例如：

• 股票买卖问题（无限交易）：贪心策略有效（每次涨就卖）。（Leetcode股票交易问题II）
• 股票买卖问题（限两次交易）：需动态规划记录状态。(Leetcode股票交易问题III)

---

五、总结

在非递减数列问题中，贪心算法的“局部”范围需包含三个元素（nums[i-2], nums[i-1], nums[i]），以确保每次修改不破坏前序递增性。这一设计体现以下原则：

1. 依赖链分析：修改的影响可能传递到更早的元素。
2. 约束完整性：局部范围需覆盖所有关键约束条件。
3. 反例验证：通过测试案例验证范围的充分性。

贪心算法的核心挑战在于如何定义“局部”。通过分析问题的依赖关系和约束传递性，可以合理划定局部范围，从而设计出高效的贪心策略。这一方法论可推广至其他问题，为算法设计提供普适性指导。