665. 非递减数列

一、题目描述

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

我们是这样定义一个非递减数列的：对于数组中任意的i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

二、解题思路

既然是非递减数列，那么就从左到右遍历数组，维护一个前面遍历过的最大值 prev，当前值 nums[i]，下一个值 next。

1. 若 nums[i] < prev，因为要求是非递减的，那么 nums[i] 是一定要修正，至少要修正到 nums[i] = prev；
2. 若 prev <= nums[i] <= next，属于正常情况，那么中值是不用修正的，直接更新 prev = nums[i]；
3. 若 prev <= nums[i] && nums[i] > next，也就是中值比两边值都大，这个时候就需要分成2种情况：一种是 prev <= next，这时候只需要修正中值 nums[i] = prev 就行了；另一种是 prev > next，这个时候修正中值是没办法满足非递减要求的，只能修正 next 的值。

同时，为了保证 prev 和 next 一直存在，就给数组左右两边分别添加了额外的最小最大值，即整数的最小最大值。

三、复杂度分析

• 时间 O(n)
• 空间 O(1)

四、参考代码

/**
 * 检查数组能否变成一个非递减数列
 * @param nums 数组
 * @return true/false
 */
private boolean checkPossibility(int[] nums) {
    int fixCount = 0;
    int prev = Integer.MIN_VALUE;
    for (int i = 0; fixCount <= 1 && i < nums.length; i++) {
        int next = i + 1 < nums.length ? nums[i + 1] : Integer.MAX_VALUE;
        // 中值比前值小，肯定要修正
        if (nums[i] < prev) {
            // 修正为 nums[i] = prev
            fixCount++;
            continue;
        }

        // 中值在前后值之间，不用修正
        if (nums[i] <= next) {
            prev = nums[i];
            continue;
        }

        // 中值最大，前值后值都比中值小
        if (prev <= next) {
            // 前值比后值小，修正中值
            // 修正为 prev <= nums[i] <= next
            fixCount++;
        } else {
            // 前值比后值大，修正后值
            prev = nums[i];
        }
    }
    return fixCount <= 1;
}