标签: 数组
难度: Medium
给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
示例 1:
输入: nums = [4,2,3] 输出: true 解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。
示例 2:
输入: nums = [4,2,1] 输出: false 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
提示：
n == nums.length1 <= n <= 104-105 <= nums[i] <= 105运行时间: 24 ms
内存: 16.9 MB
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
n = len(nums)
cnt = 0
for i in range(n-1):
if nums[i] > nums[i+1]:
cnt += 1
if cnt > 1:
return False
if i > 0 and nums[i+1] < nums[i-1]:
nums[i+1] = nums[i]
return True
题解的核心思路是遍历数组，记录出现逆序对的次数。当遍历到第i个元素时，如果发现nums[i] > nums[i+1]，即出现逆序对，此时增加计数器cnt。如果cnt超过1，则直接返回False，表示不能通过修改一个元素使数组变成非递减序列。如果是第一次遇到逆序，还需要检查nums[i+1]是否小于nums[i-1]，如果是，为了尽可能不影响后面的元素，将nums[i+1]设置为nums[i]。这样可以减小后续修改的可能性，增加成为非递减序列的机会。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
n = len(nums) # 数组的长度
cnt = 0 # 记录逆序对的数量
for i in range(n-1):
if nums[i] > nums[i+1]: # 当发现逆序对时
cnt += 1 # 增加逆序对计数
if cnt > 1: # 如果逆序对数量超过1，返回False
return False
if i > 0 and nums[i+1] < nums[i-1]: # 如果逆序对的后一个元素比前一个元素还小
nums[i+1] = nums[i] # 修改后一个元素为当前元素
return True # 如果遍历完成没有问题，则返回True
是的，直接将nums[i+1]设置为nums[i]有可能引起后续其他元素的逆序问题。这种修改方式假设提升nums[i+1]可以解决当前逆序对问题而不会对后续元素产生负面影响。然而，如果nums[i+1]本来就大于nums[i+2]，这种修改会增加新的逆序对。因此，这种策略可能并不总是最佳选择，而应视上下文和具体数组情况具体分析。
算法确实对数组的两端元素有特殊考虑。特别是当逆序对出现在数组的开头时（i=0），此时nums[i-1]不存在，因此不需要检查nums[i+1] < nums[i-1]的条件。在这种情况下，可以直接修改nums[i]为nums[i+1]或者保持不变，因为没有前一个元素与之比较。对于数组末端的元素，由于遍历到n-2停止，所以不需要特别处理最后一个元素。
决定是否将nums[i+1]调整为nums[i]或将nums[i]减小至nums[i+1]取决于nums[i-1]和nums[i+1]的关系。如果nums[i+1]小于nums[i-1]，则将nums[i+1]调整为nums[i]可能是更安全的选择，因为这样做不会影响前面的逆序状态。若没有这种情况，减少nums[i]至nums[i+1]可能是更好的选择，因为它可能减少对后续元素的潜在影响。这种决定需要根据数组的具体情况灵活处理。
此原则通过仅在绝对必要时修改元素来体现，且修改尝试最小化对数组其余部分的影响。例如，当nums[i+1] < nums[i-1]时，选择修改nums[i+1]而不是nums[i]，是为了避免对前面元素造成影响。尽管如此，可能存在更优的策略，例如，通过先进行一次扫描确定最小的修改点，或考虑使用动态规划解决多个修改点的场景。这些策略可能在特定情况下提供更优的结果，但也可能导致算法复杂度上升。