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 1 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:

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

分析：

可以visualize成如下case：

Case 1:
     7
     /\    4
    /  \  /
   /    \/
  /      3
 1
 
Case 2:

               9
              /
  7          /
  /\        /
 /  \      /
/    \    /
4      \  /
       \/
       3(i)

考虑前两个位置的ele比current ele大和小的情况，通过贪心算法，如果num[i-2]<num[i]，则改变num[i-1]就可以。

如果num[i-2]>num[i]，则改变num[i]。

Solution:

def checkPossibility(self, nums):
 “””
 :type nums: List[int]
 :rtype: bool
 “””
 count = 0
 for i in range(1, len(nums)):
   if nums[i] < nums[i-1]:
     count += 1
   if i < 2 or nums[i-2] <= nums[i]:
     nums[i-1] = nums[i]
   else:
     nums[i] = nums[i-1]
 
 return count <= 1