Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (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.
Note: The n belongs to [1, 10,000].
思路
从index=1开始遍历数组，判断nums[i]是否小于nums[i-1]，如果小，就进行下面的更换：
- i < 2 或者 nums[i] >= nums[i-2]：nums[i-1] = nums[i]
- 4, 2, 5, 6 i = 1 -> 2, 2, 5, 6
- 5, 8, 6, 9, 10 i = 2 -> 5, 6, 6, 9, 10
- 否则：nums[i] = nums[i-1]
- 4, 9, 3, 10 i = 2 -> 4, 9, 9, 10
java
class Solution {
public boolean checkPossibility(int[] nums) {
int count = 0;
if (nums.length == 0) return false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
count++;
if (count > 1) return false;
if (i - 2 < 0 || nums[i] >= nums[i-2]){
nums[i-1] = nums[i];
}else
nums[i] = nums[i-1];
}
}
return true;
}
}