题目描述

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

解题思路

在出现 nums[i] < nums[i - 1] 时,需要考虑的是应该修改数组的哪个数,使得本次修改能使 i 之前的数组成为非递减数组,并且不影响后续的操作

  1. 优先考虑令 nums[i - 1] = nums[i],因为如果修改 nums[i] = nums[i - 1] 的话,那么 nums[i] 这个数会变大,就有可能比 nums[i + 1] 大,从而影响了后续操作。
  2. nums[i] < nums[i - 2],修改 nums[i - 1] = nums[i] 不能使数组成为非递减数组,只能修改 nums[i] = nums[i - 1]
    static boolean checkPossibility(int[] nums) {
        int res = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
                res++;
            }
        }
        return res <= 1;
    }

Q.E.D.