Given an array withn
integers, your task is to check if it could become non-decreasing by modifying at most1
element.
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;
}