---

非递减数列问题详解：如何通过最优修改策略解决问题

在算法问题中，“非递减数列”是一个经典问题，其核心要求是判断在最多修改一个元素的情况下，能否将数组变为非递减数列。本文将从问题分析、策略选择到代码实现，逐步解析解决该问题的思路，并重点探讨何时修改前一个元素或当前元素的关键决策逻辑。（作者在想这部分问题时觉得画图是最直观的方式）

---

一、问题描述与示例分析

1. 问题定义

给定一个整数数组 nums，最多允许修改 1 个元素，判断是否能将其变为非递减数列。非递减数列的定义为：对于所有 0 <= i < n-1，满足 nums[i] <= nums[i+1]。

2. 示例验证

• 示例1：[4,2,3]
  输出：true
  解释：将第一个 4 改为 2，得到 [2,2,3]。

• 示例2：[3,4,2,3]
  输出：false
  解释：无论修改 4 为 2 还是修改 2 为 4，都需要至少两次修改。

---

二、问题分析与解决思路

1. 问题拆解

• 核心矛盾：当遇到递减对 nums[i-1] > nums[i] 时，必须通过修改一个元素来消除递减。
• 关键挑战：修改后需确保不破坏其他位置的递增性。

2. 贪心策略选择

每次遇到递减对时，选择对后续影响最小的修改方式：

1. 修改前一个元素 nums[i-1]：将其减小到 nums[i]。
2. 修改当前元素 nums[i]：将其增大到 nums[i-1]。
3. 便于直观理解，图解如下（作者不会平板写字轻喷）
   

---

三、关键决策逻辑：何时修改前一个元素或当前元素？

1. 决策依据：前序元素的约束

当遇到递减对 nums[i-1] > nums[i] 时，需检查 nums[i] 是否满足 nums[i] >= nums[i-2]（若 i >= 2）：

• 条件成立（nums[i] >= nums[i-2]）：
  修改前一个元素 nums[i-1] = nums[i]，确保前序递增性。
• 条件不成立（nums[i] < nums[i-2]）：
  必须修改当前元素 nums[i] = nums[i-1]，避免破坏前序递增性。

2. 逻辑推演

场景	修改策略	目的
nums[i] >= nums[i-2]	修改前一个元素	保持前序递增性
nums[i] < nums[i-2]	修改当前元素	避免引入新的递减对
i < 2（无前前元素）	可修改前一个元素	无需考虑前序约束

---

四、代码实现与解析

1. 代码实现

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int modified = 0; // 记录修改次数
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < nums[i-1]) { // 发现递减对
                if (modified++ > 0) return false; // 超过一次修改直接返回
                
                // 决策：修改前一个元素还是当前元素？
                if (i >= 2 && nums[i] < nums[i-2]) {
                    nums[i] = nums[i-1]; // 必须修改当前元素
                } else {
                    nums[i-1] = nums[i]; // 优先修改前一个元素
                }
            }
        }
        return true;
    }
};

2. 代码解析

• 遍历检查：从第二个元素开始，检查是否出现递减对。
• 修改次数限制：若修改次数超过1次，直接返回 false。
• 动态策略选择：
  • 若当前元素 < 前前元素，修改当前元素以避免破坏前序递增性。
  • 否则，修改前一个元素以最小化对后续的影响。

---

五、示例推演与策略验证

1. 示例1：[3,4,2,3]

• 遍历过程：

  1. i=1：4 > 2（递减对）。
  2. 检查 nums[2] = 2 < nums[0] = 3 → 必须修改当前元素 2 → 4，数组变为 [3,4,4,3]。
  3. i=3：4 > 3（新的递减对），此时已修改一次 → 返回 false。

• 结论：无法通过一次修改使数组成递增。

2. 示例2：[4,2,3]

• 遍历过程：
  1. i=1：4 > 2（递减对）。
  2. 无前前元素 → 修改前一个元素 4 → 2，数组变为 [2,2,3]。
  3. 后续遍历无递减 → 返回 true。

---

六、错误代码分析与改进

1. 原代码问题

// 错误逻辑：直接修改前一个元素为 nums[i]-1
if(nums[i]<nums[now]) {
    nums[now]=nums[i] - 1;
    checkNum ++;
}

• 问题：强制将前一个元素设为 nums[i]-1 可能破坏前序递增性（如 [3,4,2] 修改为 [3,1,2] 导致新的递减）。

2. 改进关键

• 动态策略选择：根据前序元素的值决定修改位置。
• 避免破坏性修改：确保每次修改后不影响已处理的部分。

---

七、总结

通过动态选择修改前一个或当前元素的策略，可以在单次遍历中高效解决问题。核心在于：

1. 前序约束检查：利用 nums[i-2] 判断修改的安全性。
2. 贪心决策：每次修改以最小化对后续的影响。

该算法的时间复杂度为 O(n)，空间复杂度为 O(1)，适用于大规模数据场景。理解策略选择的逻辑依据，是掌握此类问题的关键。

思考：

贪心算法是从局部最优解推导至整体最优解，很明显，划分“局部”的范围尤其重要，我最开始思考的时候以为最小的“局部”只需要考虑相邻的两个元素，而本题需要考虑至少三个元素才能实现从局部到整体的最优解，那么如何确定贪心算法中这个“局部最优”的“局部”范围呢？