2019-07-07 LeetCode 665 非递减数列

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。

示例 1:

输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
说明:  n 的范围为 [1, 10,000]。

首先应该先读懂题目，要求是非递归数列，也就是说需要数列是递增或者相等。
即前面的数应该小于或者等于后面的数。
用表达式表示就是array[i] <= array[i+1]而且题目中要求最多只改变一个元素。所以我们需要记录一下出现array[i] > array[i+1]等价于array[i] < array[i-1]的次数，一旦次数大于1，就直接返回 False 了。
当出现array[i] < array[i-1]的情况，我们需要判断的是 i和i-2的大小关系，如果 i<i-2 比如 3 4 2 6，那么将2 置成 4就可以了，3 4 4 6是符合的，即array[i-1] = array[i]。
i>= i-2时，比如2 4 2 6，只需要把4置成2就可以了，2 2 2 6是符合的，即array[i] = nums[i-1]。
所以根据上面的分析，Java 的代码如下

class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;
        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;
    }
}