LeetCode 665. 非递减数列

约 4 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为 快手
标签
数组

题目描述

✅ 665. 非递减数列

image-20260928224438560

题意分析

判断能否最多修改一个元素，使每对相邻元素都满足前者不大于后者。相等是合法的，原数组已经非递减时可以不修改。下面通过实际调整数组验证是否可行，因此函数会修改输入。

解法：一次修改贪心

核心思路

[!blue]

从左向右检查，保持已经处理的前缀非递减。若 nums[i - 1] <= nums[i]，当前顺序正确；否则这两个相邻位置至少要改一个，修改其他位置无法消除它们之间的下降。

优先把前一个值降为当前值，即 nums[i - 1] = nums[i]。这样当前值保持较小，后面的元素更容易接上。但下降后的前一个值还必须不小于 nums[i - 2]，所以只有 i < 2，或 nums[i] >= nums[i - 2] 时才能这样改。

如果 nums[i] < nums[i - 2]，要降低前一个值，就会同时要求它不小于 nums[i - 2] 且不大于 nums[i]，两个条件无法兼得。此时只能提高当前值，设为 nums[i - 1]，这是维持前缀有序所需的最小值，也给后续留下最多余地。

因此，每次修复都在保证前缀有序的前提下，让接下来要承接的值尽量小。若在修复后的数组上又出现下降，就需要第二次修改，而第一次采用的其他合法改法不会更有利，故可以返回 false。扫描结束且没有超过一次修改，就找到了可行方案。

解题步骤

  1. 初始化修改次数 count = 0，从下标 1 开始检查相邻元素。
  2. 若当前值不小于前值，直接继续。
  3. 出现下降时将 count 加一；若超过 1，立即返回 false。
  4. 若没有再前一个元素，或当前值不小于它，降低前值；否则提高当前值。
  5. 后续比较使用实际修改后的数组。遍历完成返回 true。

代码实现

// 若 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)$，单向扫描。
  • 空间复杂度：$O(1)$，修改写入输入数组。

关键点总结

[!green]

  • 第一次下降只能通过修改这对相邻元素之一来修复。
  • 能降低前值时优先降低；不能降低时，提高当前值到刚好满足前缀顺序即可。
  • 后续检查必须基于修复后的值，原数组的下降次数本身不足以决定答案。

易错点总结

[!yellow]

  • 降低前值前不检查 nums[i - 2]，会在已经扫描过的前方制造新下降。
  • 一律提高当前值，会让后续需要承接的值不必要地变大，可能错过可行方案。
  • 非递减允许相等，下降判断用 <，允许降低的边界判断用 >=。
  • 本实现不撤销修改，即使最终返回 false，输入也可能已经被改过。

相似题目

题目 难度 关联与区别
896. 单调数列 简单 原题只判断单调性，本题允许修改一个值，需要在首次下降处决定改前项还是后项。
1909. 删除一个元素使数组严格递增 简单 原题删除一项后要求严格递增，本题修改一项后只要求非递减，局部边界判定不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/34740715
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！