動機

我覺得我自己寫的很難懂，所以來看別人的

Problem

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: trueExplanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

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

 

Constraints:

  • n == nums.length
  • 1 <= n <= 104
  • -105 <= nums[i] <= 105

Sol

中間的必須在中間，所以有兩個case，太大或太小 最前面大於最後面

對應的改法是 最前面大於最後面 => 最前面改小 中間太大 => 改與前面一樣 中間太大 => 改與前面一樣

1,2,3
1,4,3
4,2,3
2,1,3

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        else:
            chance =  1
            if nums[0] < nums[1]:
                chance = 1
            else:
                nums[0] = nums[1]-1
                chance = 0
            
            for i in range(1,len(nums)-1):
                if not (nums[i-1] <= nums[i] <= nums[i+1]):
                    if chance == 0:
                        return False
                    if chance != 0:
                        chance -= 1
                        if nums[i-1] > nums[i+1]:
                            if nums[i] >= nums[i-1]:
                                nums[i+1] = nums[i]
                            else:
                                return False
                        else:
                            nums[i] = (nums[i-1]+nums[i+1])//2
            return True

但我覺得我自己寫的很難懂，所以來看別人的 如果出事的話，兩個case

  1. 前面太大，像1,4,3，所以要看arr[i-2]與arr[i]的大小
  2. 現在太小，不是前面太大就是現在太小
 public boolean checkPossibility(int[] nums) {
        int cnt = 0;                                                                    //the number of changes
        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-1] = nums[i];                    //modify nums[i-1] of a priority
                else nums[i] = nums[i-1];                                                //have to modify nums[i]
            }
        }
        return cnt<=1; 
    }