1.原题地址

2.方法一

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

这是题干，注意看条件，最多改变1个元素，也就是说遍历数组，如果遇到nums[i]>nums[i+1]，就要改变两个中的一个。然后看改变后的数组是否是一个非递减数组。

那么问题来了，改变两个中的哪一个呢？

比如,
对于数组nums=[1,2,3,2]且i=2时，应该改变nums[i+1]
对于数组nums=[3,1,2,4]且i=0时，应该改变nums[i]

所以改变哪一个都是有可能使数组变为非递减数组的。

至于怎么改变，我也想了很久，后来我才悟到：
其实根本不需考虑太多，既然不知道改变哪一个，我都试一下不就行了吗？！！

思路

  • 遍历数组，如果遇到nums[i]>nums[i+1]的；
  • 先令nums[i+1] = nums[i]（此处要用变量记下nums[i+1]以及i+1）；
  • 然后再遍历数组验证是否满足非递减条件；
  • 如果满足直接返回True；
  • 如果不满足将数组恢复原状，再令nums[i] = nums[i+1]；
  • 再次遍历数组验证是否满足非递减条件；

代码

  1. class Solution:
  2.     def checkPossibility(self, nums: List[int]) -> bool:
  3.         n = len(nums)
  4.         for i in range(n-1):
  5.             if nums[i] > nums[i+1]:  # 找到了第一个nums[i]>nums[i+1]
  6.                 temp = nums[i+1]
  7.                 tid = i+1
  8.                 nums[i+1] = nums[i]  # 改变nums[i+1]
  9.                 break
  10.         # 验证数组是否非递减
  11.         flag = 0
  12.         for i in range(n-1):
  13.             if nums[i] > nums[i+1]:
  14.                 flag = 1
  15.                 break
  16.         if flag == 0:    return True
  18.         nums[tid] = temp        # 将数组恢复原状
  19.         nums[tid-1] = temp     # 改变nums[i]
  20.         # 验证数组是否非递减
  21.         for i in range(n-1):
  22.             if nums[i] > nums[i+1]:
  23.                 return False
  24.         return True

时空复杂度

三个for循环，时间复杂度为O(3*N) = O(N)
定义了几个变量，空间复杂度为O(1)

3.方法二—贪心算法

对于一个数组，如果遇到nums[i]>nums[i+1]的情况，并且现在要你改变其中一个使其成为非递减数组，你会怎么选择呢？

思路

因为遇到nums[i]>nums[i+1],就说明i之前的部分都是非递减的（包括i），为了使这个非递减序列更够更长，我们会倾向于使nums[i+1] = nums[i]，因为如果使nums[i] = nums[i+1]的话，就有可能破坏掉i之前的非递减结构了。

但是有一种情况是例外的：
考虑数组nums = [1,2,8,4,5]且i=2时，因为nums[i] > nums[i+1] and nums[i] > nums[i+2]，所以如果还按我们的思路来改变nums[i+1] = 8，那么等到了后面还是会出错，所以此时我们应该让nums[i] = nums[i+1]。

总结来说，遇到nums[i]>nums[i+1]，我们倾向于使**nums[i+1] = nums[i]，除非nums[i] > nums[i+1] and nums[i] > nums[i+2]。**

代码

  1. class Solution:
  2.     def checkPossibility(self, nums: List[int]) -> bool:
  3.         n = len(nums)
  4.         for i in range(n-1):
  5.             if nums[i] > nums[i+1]:
  6.                 if i+2 < n and nums[i] > nums[i+2]:  # 特殊情况
  7.                     nums[i] = nums[i+1]
  8.                 else:  # 常规情况
  9.                     nums[i+1] = nums[i]
  10.                 break
  11.         for i in range(n-1):
  12.             if nums[i] > nums[i+1]:
  13.                 return False
  14.         return True

时空复杂度

同方法一