Description
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].
Solution
Greedy
一开始思路就挺上道的，想到把unsorted的值改掉，而且还要考虑nums[i - 2]的问题，但想着想着就晕了...
对于一个数组：a0, a1, a2, a3, a4
如果遍历到a3时发现a3 < a2，我们必须修改a3或者a2来保持有序，这时采用贪心算法决定该谁更优：
- 如果a3 > a1：a2 = a3即可，将a2改小都可以满足条件。
- 如果a3 < a1：则必须a3 = a2，将a3改大才能满足条件。
贪心的策略是，使修改过后a3越小越好，这样更有利于后面有序，毕竟需要a3 <= a4。
class Solution {
public boolean checkPossibility(int[] nums) {
boolean unsorted = false;
for (int i = 1; i < nums.length; ++i) {
if (nums[i] < nums[i - 1]) {
if (unsorted) {
return false;
}
unsorted = true;
if (i > 1 && nums[i] < nums[i - 2]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}
}
}
return true;
}
}
