非递减数列最多修改一次如何用贪心判断？（LeetCode 665）

简化版

扫描数组，遇到 nums[i-1] > nums[i] 就发现一次下降违规；违规次数超过 1，直接 false。

只有一次违规时，优先降低 nums[i-1]，但如果 nums[i-2] > nums[i]，降低前一个会破坏更早关系，只能升高 nums[i]。

详细版

非递减数组要求每个相邻对满足 nums[i-1] <= nums[i]。最多只能修改一个数，所以扫描中最多允许出现一次下降。

遇到下降 nums[i-1] > nums[i] 时，有两个修复方向：把前一个数降到 nums[i]，或把当前数升到 nums[i-1]。如果 i < 2 或 nums[i-2] <= nums[i]，说明降低 nums[i-1] 不会破坏左侧关系，优先这样做；否则只能升高 nums[i]。

boolean checkPossibility(int[] nums) {
    int cnt = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i - 1] <= nums[i]) continue;
        if (++cnt > 1) return false;
        if (i < 2 || nums[i - 2] <= nums[i]) {
            nums[i - 1] = nums[i];
        } else {
            nums[i] = nums[i - 1];
        }
    }
    return true;
}

完整版教学

一、为什么只关注下降位置

非递减条件是局部相邻关系：nums[i-1] <= nums[i]。只要所有相邻对都满足，整个数组就满足；一旦出现 nums[i-1] > nums[i]，就必须通过修改这两个数之一来修复。因为其他位置的数无法改变这对相邻关系。

最多修改一次意味着下降违规不能出现两次以上。即使两次下降共享某个元素，也要谨慎判断，但线性扫描中的修复会把唯一修改机会用掉，后面再遇到下降就一定失败。

二、一次违规有两种修法

遇到形如 a, b 且 a > b 的相邻对，修复方式只有两类：降低 a 或升高 b。降低 a 通常更好，因为它让当前值更小，不会给后续造成更高门槛；但降低 a 可能破坏它和前一个数的关系。

... nums[i-2], nums[i-1], nums[i]
        x          a          b
违规: a > b
方案1: 降低 a 到 b，需要 x <= b
方案2: 升高 b 到 a，保住 x <= a

这个局部判断就是贪心的核心：能降前一个就降前一个，不能降才升当前。

三、为什么优先降低前一个数

降低 nums[i-1] 会让当前位置的前缀尽量低，给后面的元素留下更宽松的非递减空间。例如 [4,2,3] 中，遇到 4 > 2，把 4 降成 2 得到 [2,2,3]，合法；如果把 2 升成 4 得到 [4,4,3]，后面又违规。

这体现了贪心的「降低门槛」思想。只要不破坏左边，降低前一个数永远不会让右边更难处理；升高当前数则可能让后续必须更大。

四、什么时候不能降低前一个数

如果 nums[i-2] > nums[i]，把 nums[i-1] 降到 nums[i] 会导致 nums[i-2] > nums[i-1]，左侧关系被破坏。此时只能把当前数 nums[i] 升到 nums[i-1]。

以 [3,4,2,5] 为例，遇到 4 > 2。如果把 4 降成 2，得到 [3,2,2,5]，3 > 2 仍违规；正确做法是把 2 升成 4，得到 [3,4,4,5]。

数组	违规	可行修法	原因
`[4,2,3]`	`4>2`	降低 4	左侧不存在约束
`[3,4,2,5]`	`4>2`	升高 2	`3>2`，不能降 4
`[1,4,2,3]`	`4>2`	降低 4	`1<=2`，左侧安全

五、数字例子完整走查

看 [1, 4, 2, 3]：

i=1: 1 <= 4，正常
i=2: 4 > 2，第一次违规
     nums[i-2]=1 <= nums[i]=2，可以降低前一个
     数组变为 [1,2,2,3]
i=3: 2 <= 3，正常
返回 true

再看 [4, 2, 1]。4 > 2 用掉一次修改机会，修成 [2,2,1] 或 [4,4,1] 后，最后仍会出现下降，因此返回 false。算法扫描时第二次遇到违规，直接失败。

六、是否必须真的修改数组

可以真的修改数组，这样逻辑最直观。也可以只维护上一个有效值来避免改变输入，但代码会更绕。面试中若题目没有禁止修改输入，直接原地修改更容易解释。

记忆钩子：一次下降看三格，x, a, b 中 a>b；若 x<=b 就降 a，否则升 b。

七、常见误区与追问

误区：只统计下降次数即可。 有一次下降也可能不可修，必须判断该改前一个还是当前。
误区：永远把当前数升高。 可能抬高后续门槛，导致本可通过的数组失败。
误区：永远把前一个数降低。 当 nums[i-2] > nums[i] 时会破坏左侧关系。
追问：为什么超过一次下降一定失败？ 每次下降至少需要改相邻两数之一，修改一次最多可靠修复一个独立违规点。
追问：复杂度是多少？ 扫描一次，时间 O(n)，原地修改空间 O(1)。
追问：能不能不修改原数组？ 可以维护逻辑上的前一个值，但实现复杂度略高，核心判断不变。

八、加强记忆

非递减数组这题的锚点是「一次下降，三格判断」。遇到 a > b 时，先想能不能把 a 降低，因为降低前一个会让后续更轻松；判断条件是左边的 x <= b。如果左边已经比 b 大，就不能降 a，只能升 b。全程最多允许一次违规，第二次违规直接失败。记住「能降则降，不能降才升」，就抓住了贪心修复的本质。

简化版

详细版