LeetCode 665. 非递减数列

2021-07-20 HGNULB 约 8 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 665. 非递减数列

题意分析

给一个整数数组，问能不能最多改动其中一个元素，让整个数组变成非递减的。非递减允许相邻相等，不要求严格递增，这一点写错会让大量本来合法的输入被判死。

「最多改动一个」有两层含义：一是原本就有序时一次都不用改，也算通过；二是改动是把某个位置替换成任意整数，不是加一减一，也不是和别的位置交换，所以可选的新值不受数组里已有值的限制。

约束是 n 最大一万级、元素可正可负，量级上留给 $O(n)$ 或 $O(n \log n)$ 都够，但 $O(n^2)$ 在极端数据下会吃紧。真正的难点不在复杂度，而在于「改哪个、改成多少」这个决策：同一处不合法可以通过改前一个数或改后一个数来化解，两种改法对后续的影响完全不同。

边界上要留意：长度不超过 2 的数组必然可以通过一次改动变成非递减，答案恒为真；数组里可以有重复值，重复不构成不合法；全部相等也是合法的非递减数组。

解法：一次修改贪心

核心思路

暴力做法是枚举被改的下标，再枚举它改成什么值。值域是无限的，但稍加分析就知道候选值只有两个有意义——改成前一个元素的值或改成后一个元素的值——于是枚举量降到 $O(n)$ 种方案，每种方案再花 $O(n)$ 校验一遍，总共 $O(n^2)$。一万的数据能过，但这套做法完全没有利用问题结构。

瓶颈在于反复的全量校验。换个角度看，数组不合法只体现在若干个「相邻逆序」的位置上，也就是满足 nums[i] < nums[i-1] 的那些 i。一次修改最多能消除一个这样的位置：修改下标 j 只会影响 (j-1, j) 与 (j, j+1) 这两个相邻对，而这两个对如果同时逆序，说明 nums[j+1] < nums[j] < nums[j-1]，无论把 nums[j] 改成什么，都不可能同时不小于 nums[j-1] 又不大于 nums[j+1]。所以只要逆序位置的个数达到 2，答案立刻是假。

于是问题收缩成：逆序位置恰好一个时，该怎么改才不会给后面留下隐患。设逆序发生在下标 i，也就是 nums[i] < nums[i-1]。可选的补救有两种：把 nums[i-1] 压低到 nums[i]，或者把 nums[i] 抬高到 nums[i-1]。前者让当前位置的值尽可能小，对后面最友好，所以应当优先；但它有前提——压低之后 nums[i-1] 不能小于它自己的前驱 nums[i-2]，也就是必须满足 nums[i] >= nums[i-2]。当 i < 2 时不存在前驱，前提自动成立。若前提不成立，就只能退而求其次抬高 nums[i]，此时当前位置的值被迫变大，但这是唯一的合法选择。

支撑这套贪心的不变量是：每次处理完下标 i 之后，前缀 nums[0..i] 已经是非递减的，count 等于让这个前缀合法所必需的最少修改次数，并且在所有能达成这个次数的方案里，nums[i] 被压到了尽可能小的值。最后一句是贪心成立的关键——正因为每一步都给后面留下了最宽松的下界，才不需要回头重试另一种改法。

解题步骤

用 count 记录已经用掉的修改次数，从下标 1 开始向右扫描，逐个检查 nums[i] < nums[i-1] 是否成立。

一旦发现逆序就让 count 加一，并立即判断 count > 1，成立则直接返回假。提前返回不只是省时间，也避免了在已经无解的数组上继续做无意义的修改。

接着做修改决策：若 i < 2 或 nums[i] >= nums[i-2]，执行 nums[i-1] = nums[i]，把前一个元素压下来。这是首选方案，因为它不改变 nums[i]，给后续留下的下界最小。

否则执行 nums[i] = nums[i-1]，把当前元素抬上去。此时压低会让 nums[i-1] 掉到 nums[i-2] 以下，制造出新的逆序，反而更糟。

修改必须真的写回数组，不能只计数。因为后续的比较依赖修改后的值，只数不改会让本该暴露的第二处逆序被掩盖。

扫描结束后返回真。能走到这里说明逆序至多发生过一次且已被合法修复。

以 nums = [1, 4, 2, 3] 走一遍：i = 1 时 4 不小于 1，合法，跳过。i = 2 时 2 < 4 逆序，count 变成 1，没有超限；接着判断补救方式，此时 i 不小于 2，比较 nums[2] = 2 与 nums[0] = 1，2 不小于 1，前提成立，于是压低前一个元素，执行 nums[1] = 2，数组变成 [1, 2, 2, 3]。i = 3 时 3 不小于 nums[2] = 2，合法。扫描结束，count 为 1，返回真。作为对照，把输入换成 [3, 4, 2, 3]：i = 2 处同样逆序，count 变成 1，但这次 nums[2] = 2 小于 nums[0] = 3，压低会让下标 1 的元素掉到 3 以下从而与下标 0 冲突，只能走抬高分支，执行 nums[2] = 4，数组变成 [3, 4, 4, 3]；随后 i = 3 处 3 < 4 又一次逆序，count 变成 2 超过上限，返回假。这两组输入的逆序位置个数完全相同，结果却相反，正说明了为什么必须把修改真正落到数组上。

代码实现

// 若 i < 2 或 nums[i] >= nums[i-2]，则下调 nums[i-1]。
class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                count++;
                if (count > 1) {
                    return false;
                }

                if (i < 2 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }

        return true;
    }
}

// 若 i < 2 或 nums[i] >= nums[i-2]，则下调 nums[i-1]。
func checkPossibility(nums []int) bool {
    count := 0

    for i := 1; i < len(nums); i++ {
        if nums[i] < nums[i-1] {
            count++
            if count > 1 {
                return false
            }

            if i < 2 || nums[i] >= nums[i-2] {
                nums[i-1] = nums[i]
            } else {
                nums[i] = nums[i-1]
            }
        }
    }

    return true
}

复杂度分析

时间复杂度：$O(n)$，其中 n 是数组长度。只做一趟扫描，每个下标上的比较与赋值都是常数级，无解时还会提前返回。

空间复杂度：$O(1)$，只用了一个计数器；修改直接落在输入数组上，没有开任何辅助结构。需要注意这意味着函数会改动调用方传入的数组，在不允许副作用的场景下要先拷贝一份。

关键点总结

「最多改一次」这类题的第一步永远是给违规次数定上界：先证明一次修改最多消除一个相邻逆序，于是逆序数达到 2 就可以立刻否定，问题瞬间从搜索退化成判定加一次决策。

决策点上有两个候选时，贪心要挑「给后续留下的约束最宽松」的那个。本题里压低前一个元素不改变当前值，因此后续的下界更小，是默认选择；只有当它会破坏更前面的顺序时才改用抬高。

贪心的正确性要靠不变量说话：每一步之后前缀合法、修改次数最少、且末元素取到可行的最小值。第三条是不需要回溯的根本原因，答题时必须点出来。

修改要真正写回数组，因为后续判断依赖被修改后的值；「只统计逆序个数」是一个看起来能过样例、实际上完全错误的简化。

面试视角：面试官几乎必然拿 [4,2,3] 和 [3,4,2,3] 这一对来考你——两者都只有一处逆序，答案却一真一假。能主动说出这组对照，等于直接证明你理解了「改哪一个」才是本题的核心，而不是背了个模板。

面试视角：被追问「为什么两处逆序一定无解」时，要给出那句反证——若下标 j 的左右两侧都逆序，则 nums[j+1] < nums[j-1]，改动任何单个位置都无法同时满足两侧；口头证一遍比说「经验如此」有力得多。

易错点总结

错误写法：只统计逆序位置的个数、不真正修改数组：nums = [3, 4, 2, 3] → 逆序只在下标 2 出现一次，计数为 1 就返回真，而正确答案是假。

错误写法：遇到逆序一律压低前一个元素：nums = [3, 4, 2, 3] → 把 4 压成 2 得到 [3, 2, 2, 3]，下标 1 与下标 0 之间新产生的逆序没人再检查，返回真，正确答案是假。

错误写法：遇到逆序一律抬高当前元素：nums = [4, 2, 3] → 把 2 抬成 4 得到 [4, 4, 3]，下标 2 处又逆序，计数变成 2 返回假，而正确答案是真。

错误写法：压低的前提条件写成严格大于 nums[i] > nums[i-2]：nums = [2, 3, 2, 2] → 相等的情形被排除，被迫走抬高分支得到 [2, 3, 3, 2]，尾部再次逆序返回假，而把 3 改成 2 显然可行，正确答案是真。

错误写法：把非递减误当成严格递增，判断条件写成 nums[i] <= nums[i-1]：nums = [1, 1, 1] → 两处相等被当成违规，计数超限返回假，而这个数组本身就是合法的非递减数组。

错误写法：漏掉 i < 2 这个短路条件，直接访问 nums[i-2]：nums = [3, 1] → 在 i = 1 处读到下标 -1，抛出数组越界。

错误写法：把上限判断写成 count > 2：nums = [3, 2, 1] → 下标 1 和 2 处各有一次逆序，计数到 2 仍被放行，返回真，而这个数组改一个数无论如何都救不回来。

相似题目

题目	难度	考察点
941. 有效的山脉数组	简单	只校验先升后降的形状，不允许任何修改，重点在两端退化情形
581. 最短无序连续子数组	中等	同样围绕单调性缺陷，但要定位出需要重排的最短区间
926. 将字符串翻转到单调递增	中等	允许多次修改并求最少次数，需要按分界点做前后缀统计
300. 最长递增子序列	中等	求保留的最长单调子序列，贪心配合二分而非局部修补