[Java] LeetCode 665. Non-decreas

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

  即问是否可以在最多改变一个数组元素的情况下，保持原数组单调不减

Solution

法1： With Modifying Input

e.g.

• 2 4 2 6 ∵2 == 2 ∴4 → 2
• 3 4 2 6 ∵3 > 2 ∴2 → 4

1. 类似贪心，一边遍历数组，一边判断是否符合条件，并修改相应index的元素;
2. 修改次数 <=1;
3. 若发现nums[i-1] > nums[i]，此时再比较 nums[i-2] 和 nums[i]的大小， 尽量朝小的改，即修改为 nums[i-1] = nums[i] 的优先级大于 nums[i] = nums[i-1]

class Solution {
   public boolean checkPossibility(int[] nums) {
    int count = 0;    //the number of changes
    for(int i = 1; i < nums.length && count<=1 ; i++){
        if(nums[i-1] > nums[i]){
            count++;
            if(i-2<0 || nums[i-2] <= nums[i]) nums[i-1] = nums[i];    //modify nums[i-1] of a priority
            else nums[i] = nums[i-1];                                //have to modify nums[i]
        }
    }
    return count<=1; 
｝  
}

法2： Without Modifying Input

1. 用prev指针代表 nums[i-1];
2. 若 nums[i - 2] > nums[i] ,则prev指向不变，作用相当于令 nums[i] = nums[i-1]；否则prev指向当前元素，即nums[i-1] = nums[i]

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