Non-decreasing Array

Given an array with n integers, your task is to check if it could become non-deceasing by modifying at most1element.

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

Example 1:

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

Example 2:

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

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

The meaning of the title is to find a shortest non-descending subsequence. We can give a few examples to summarize:

Sequence: 1 4 2 3

In our thinking, there must be a process of comparing the magnitude of the two values ​​before and after, which is correct, because if the sequence that begins to descend does not meet the requirements of the answer, just like when the loop reaches 2, we find that the4 is small, the sequence begins to decline, so we need to change the value here, which one to change, this is the point.Here we also need to give an example, you will see later

Sequence 3 4 2 5

We find that when we loop to 2, the previous 3 is greater than 2, while the first example is 1, which is smaller than 2.In sequence 1, because nums[i-2]<=nums[i], it means that only the first 4 does not satisfy the increment, so we need to change 4 to 2.In the second sequence, nums[i-2]>=nums[i], so it is necessary to turn 2 into 4 to satisfy.

So we can get ideas:

When nums[i-2]>=nums[i]: nums[i]=nums[i-1]

When nums[i-2]<=nums[i]: nums[i-1]=nums[i]

And when arr[i]1, it returns false, because it can only be adjusted once

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]1):return Falseif i-2<0 or nums[i-2]<=nums[i]:nums[i-1]=nums[i]else:nums[i]=nums[i-1]return True