665. 非递减数列

1. 题目简介

难度：中等，原题链接：665. 非递减数列。

给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

2. 问题分析

非递减数列是指每个元素都不大于后一个元素，即所有相邻位置都满足 nums[i] <= nums[i + 1]。

找到第一处 nums[i] > nums[i + 1] 后，只需尝试修改这两个元素之一。因为修改其他位置无法消除这一对元素的逆序，而题目最多允许修改一次。

两种选择都可能有用：

• [1, 2, 1, 1] 需要降低下标 1 的值，得到 [1, 1, 1, 1]。如果提高后一个 1，后面仍然会出现逆序。
• [3, 4, 2, 5] 需要提高下标 2 的值，得到 [3, 4, 4, 5]。如果只降低 4，它既要不小于前面的 3，又要不大于后面的 2，无法同时满足。

代码分别尝试修改下标 i 和 i + 1。对于待修改的位置，有前驱时就把它设为前驱的值，这是保持左侧非递减所允许的最小值，也给右侧留下了最大的选择范围。修改头部时没有前驱，代码使用 Integer.MIN_VALUE。

每次尝试后都重新检查整个数组，并恢复被修改的值，避免影响下一次尝试。如果两种选择都失败，就无法只改一个元素完成；如果原数组没有逆序，则直接返回 true。

3. 代码实现

class Solution {
    public boolean checkPossibility(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return check(nums, i) || check(nums, i + 1);
            }
        }
        return true;
    }

    private boolean check(int[] nums, int i) {
        int tmp = nums[i];
        nums[i] = i == 0 ? Integer.MIN_VALUE : nums[i - 1];
        boolean flag = true;
        for (int j = 0; j < nums.length - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                flag = false;
                break;
            }
        }
        nums[i] = tmp;
        return flag;
    }
}

4. 复杂度分析

• 时间复杂度：O(n)。寻找第一处逆序后，最多再做两次完整检查，扫描次数是常数。
• 空间复杂度：O(1)。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明