题目

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).

给定一个整数数组，判定是否最多修改一个位置上的数字就可以让这个数组变成递增数组（包含等号）。

解析

基本思想是贪心算法，碰到一个不符合要求的就恢复一个，如果修复次数多于一次则返回false
需要处理的就是发生后一个数小于前一个数的部分，比如 [3 4 2] 中 4 和 2是冲突的。
标记为 ai-2, ai-1, ai，发生冲突后可以用两种方法进行修复（肯定能修复）：

1. 如果ai-2 > ai，则需要做ai = ai-1的修改，如 3 4 2
2. 否则做ai-1=ai的修改，因为局部修改可以防止后面的出现问题，如1 4 2 3

代码

public boolean checkPossibility(int[] nums) {
    if(nums == null || nums.length == 0) return false;

    int cnt = 0;  //修复次数
    for(int i = 1; i < nums.length && cnt <= 1; ++i){
        if(nums[i-1] > nums[i]){
            cnt ++;
            //做出修复
            if(i - 2 >= 0 && nums[i-2] > nums[i]){  //这种情况只能对nums[i]进行修复
                nums[i] = nums[i-1];
            }else{  //一般选择对nums[i-1]进行修复
                nums[i-1] = nums[i];
            }
        }
    }

    return cnt <= 1;
}