难度：中等

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

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

解题思路

• 假如元素 i 需要改变，修改 i 的值可能会导致 i – 1 与 i 的结果发生变化，因此优先修改 i + 1；
• 为了保证 i + 2 尽可能减少影响，那么将选择最接近 i 的值来赋值；

题解

public boolean checkPossibility(int[] nums) {
    int invalidElement = 0;

    int current;
    int next;
    for (int i = 0, lastIndex = nums.length - 1; i < lastIndex; i++) {
        current = nums[i];
        next = nums[i + 1];

        if (current > next) {
            ++invalidElement;
            if (invalidElement > 1) {
                return false;
            }

            // 当 current > next 时, 因为 current 需要大于 prev，则 current 为 next最佳
            // prev <= current && current <= next, 所以 prev <= next
            if (i > 0 && nums[i - 1] > next) {
                nums[i + 1] = current;
            }
        }
    }
    return true;
}
复制代码

思路

NonDecreasingArray nonDecreasingArray = new NonDecreasingArray();

@Test
public void test_case1() {
    Assertions.assertTrue(nonDecreasingArray.checkPossibility(new int[]{4, 2, 3}));
}

@Test
public void test_case2() {
    Assertions.assertFalse(nonDecreasingArray.checkPossibility(new int[]{4, 2, 1}));
}

@Test
public void test_case3() {
    Assertions.assertFalse(nonDecreasingArray.checkPossibility(new int[]{3, 4, 2, 3}));
}

@Test
public void test_case4() {
    Assertions.assertTrue(nonDecreasingArray.checkPossibility(new int[]{5, 7, 1, 8}));
}
复制代码