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