Difficulty: Medium

Given an array of integers of length n, determine whether the array can become a non-decrement array with the most variable 1 element.

We define a nondecreasing sequence like this: for any I in the array (0 <= I <= n-2), nums[I] <= nums[I + 1].

Their thinking

• If element I needs to be changed, changing the value of I may cause the results of i-1 and I to change, so I + 1 is preferred.
• To ensure that I + 2 has as little impact as possible, the value closest to I will be assigned;

Answer key

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;
            }

            // When current > next, because current needs to be greater than prev, current is best for next
            // prev <= current && current <= next, 所以 prev <= next
            if (i > 0 && nums[i - 1] > next) {
                nums[i + 1] = current; }}}return true;
}
Copy the code

Train of thought

NonDecreasingArray nonDecreasingArray = new NonDecreasingArray();

@Test
public void test_case1(a) {
    Assertions.assertTrue(nonDecreasingArray.checkPossibility(new int[] {4.2.3}));
}

@Test
public void test_case2(a) {
    Assertions.assertFalse(nonDecreasingArray.checkPossibility(new int[] {4.2.1}));
}

@Test
public void test_case3(a) {
    Assertions.assertFalse(nonDecreasingArray.checkPossibility(new int[] {3.4.2.3}));
}

@Test
public void test_case4(a) {
    Assertions.assertTrue(nonDecreasingArray.checkPossibility(new int[] {5.7.1.8}));
}
Copy the code