665. Non-decreasing Array

---

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• -10^5 <= nums[i] <= 10^5

---

解法1

非递减数列, 即没有nums[i] > nums[i+1]的情况出现的数列. 那么如果碰到这种情况, 有两种处理方式

1. nums[i] 变小
2. nums[i+1]变大

class Solution {
    public boolean checkPossibility(int[] nums) {
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i] > nums[i+1]){
                int temp1 = nums[i] , temp2 = nums[i + 1];
                nums[i] = temp2;
                if(checkBefore(nums, i) && checkAfter(nums, i + 1))
                    return true;
                nums[i + 1] = temp1;
                if(checkAfter(nums, i + 1))
                    return true;
                return false;
            }
        }
        return true;
    }
    
    private boolean checkBefore(int[] nums, int k){
        for(int i = k; i > 0; i--)
            if(nums[i - 1] > nums[i])
                return false;
        return true;
    }
    
    private boolean checkAfter(int[] nums, int k){
        for(int i = k; i < nums.length - 1; i++)
            if(nums[i] > nums[i + 1])
                return false;
        return true;
    }
}

解法2

其实不用这么麻烦. 在位置i时, 有一个默认的前提就是 0 到 i -1 的位置都是非递减的. 那么也就是说上述的checkBefore其实并不需要. 在位置 i 时, 其实只需要注意 i - 1, i 和 i + 1 三个值就可以了.

class Solution {
    public boolean checkPossibility(int[] nums) {
        
        int count = 0;
        
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i] > nums[i+1]){
                count++;
                if(count > 1)
                    return false;
                if(i > 0 && nums[i - 1] > nums[i + 1])
                    nums[i + 1] = nums[i];
                else
                    nums[i] = nums[i + 1];
            }
        }
        return true;
    }
}