Given an array withnintegers, your task is to check if it could become non-decreasing by modifying at most1element.

We define an array is non-decreasing ifarray[i] <= array[i + 1]holds for everyi(1 <= i < n).

Example 1:

Input: [4,2,3]

Output: True

Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1]

Output: False

Explanation: You can't get a non-decreasing array by modify at most one element.

Solution: When you findnums[i-1] > nums[i]for somei, you will prefer to changenums[i-1]'s value, since a largernums[i]will give you more risks that you get inversion errors after positioni. But, if you also findnums[i-2] > nums[i], then you have to changenums[i]'s value instead, or else you need to change both ofnums[i-2]'s andnums[i-1]'s values.

    public boolean checkPossibility(int[] nums) {
        int count = 0;
        for (int i = 1; i < nums.length && count < 2; i++) {
            if (nums[i - 1] > nums[i]) {
                count++;
                if (i - 2 < 0 || nums[i - 2] <= nums[i]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        return count < 2;
    }

results matching ""

    No results matching ""