Non-decreasing Array

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

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

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

Example 2:

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

Note: The n belongs to [1, 10,000].

题目的意思就是寻找一个最短的不下降子序列，我们可以举几个例子来总结一下：

序列：1 4 2 3 

我们的思路中一定是有比较前后两个值的大小的过程，这是没错的，因为如果开始下降的序列就是不符合答案要求了，就像循环到2的时候，我们发现比4小，序列开始下降，所以我们在这里是需要换数值了，那到底是换哪个呢，这才是重点。这里我们还需要举一个例子，大家看后面

序列   3  4  2  5

我们发现这里当我们循环到2的时候，前面的3是大于2的，而第一个例子是1，比2小。序列一的时候，我们因为nums[i-2]<=nums[i]，说明只有前面的4不满足递增，所以我们需要把4变成2。序列二的时候，nums[i-2]>=nums[i]，所以是要把2变成4才能满足。

所以我们可以得到思路：

当 nums[i-2]>=nums[i]时：nums[i]=nums[i-1]

当nums[i-2]<=nums[i]时：nums[i-1]=nums[i]

并且当找寻到arr[i]<arr[i-1]时，说明需要调整，则index++，当index>1时，就return false，因为只能调整一次

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        index=0
        #[3,4,2,3]
        for i in range(1,len(nums)):
            if nums[i]<nums[i-1]:
                index+=1
                if(index>1):
                    return False
                if i-2<0 or nums[i-2]<=nums[i]:
                    nums[i-1]=nums[i]
                else:
                    nums[i]=nums[i-1]
        return True