每天都要刷 665 ～ 非递减数列

基本信息

• 题号：665
• 题厂：亚麻
• 难度系数：中

已知一个数列，问最多改动数列一个元素的情况下，能否上数列成为一个从头到尾不递减数列？如果可以，返回 true；不行返回 false。

例如：nums = [4,2,3]

返回 true。只要把 4 换成 1 或者其他比 1 小的整数，就完成整个数列完全非递减了……

解题思路

判断递增递减，常见思路就是遍历数组然后比较前后元素大小；

• 对于本题，如果遇上递增情况，什么也不用做……
• 如果遇上递减，查看是否使用了唯一一次的替换机会；如果已经使用了，返回 false 结束循环
• 最麻烦的就是第一次遇上递减，如何合理替换元素达到全员递增？

例如 [2,3,2,2]， 3-2 处我们遇上了递减状况，为了改变元素成为非递减，我们可以考虑降格 3 到 2，数组变为[2,2,2,2]，也可以升格 2 到 3 为 [2,3,3,2]；

如果我们选择升格 2 到 3，虽然 3-2 区间的递减问题解决了，但又会造成后续递减……所以选择谁降格谁升格问题，比较复杂……

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        # 初始计数器为 0
        count = 0
        
        for i in range(len(nums) - 1):
            # 在遍历过程中，为了让数列尽可能实现只替换一次元素完成非递减，我们优先选择降格模式；在不能降格的情况下，再升格后者……
            if nums[i] <= nums[i + 1]:
                continue
            elif count > 0:
                return False
            else:
                if i == 0 or nums[i + 1] >= nums[i - 1]:
                    nums[i] = nums[i + 1]
                else:
                    nums[i + 1] = nums[i]
                count += 1
                 
        return True       

Constraints

• n == nums.length
• 1 <= n <= 104
• -105 <= nums[i] <= 105

Big O

• Time：O（n）
• Space：O（1）

测试

• 本题可以测试的案例很多，一定要把各种情况都考虑到

总结

• 就算法难度和成型代码复杂度来说，中规中矩中档题；解题思路也非常显而易见……
• 体现难度系数考点：如何处理第一次替换元素的情况分析，以及涉及的数组边界问题和多种测试情况😵