打卡力扣题目七

关于 ARTS 的释义 —— 每周完成一个 ARTS：

● Algorithm: 每周至少做一个 LeetCode 的算法题

● Review: 阅读并点评至少一篇英文技术文章

● Tips: 学习至少一个技术技巧

● Share: 分享一篇有观点和思考的技术文章

希望通过此次活动能聚集一波热爱技术的人，延续好奇、探索、实践、分享的精神。

一、题目

给你一个长度为 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

解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

二、解题方法一

def checkPossibility(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            # 如果当前元素比下一个元素大，则需要将当前元素减小或将下一个元素增大
            # 为了只改变一个元素，我们可以将当前元素减小到比下一个元素小的最小值
            # 或者将下一个元素增大到比当前元素大的最小值
            # 因此，我们只需要找到这两个数中的最小值即可
            return min(nums[i], nums[i + 1]) < max(nums[i], nums[i + 1])
    # 如果所有元素都满足非递减的条件，则返回 True
    return True

这段代码实现了一个函数 `checkPossibility`,用于判断在最多改变 1 个元素的情况下，给定的整数数组是否能变成一个非递减数列。

函数的输入参数为一个整数数组 `nums`。

首先，我们使用一个循环遍历数组中的每个元素 `i`,并检查当前元素 `nums[i]` 是否比下一个元素 `nums[i + 1]` 大。如果是，则说明当前元素需要被修改，以使得整个数组能够变成非递减数列。

为了只改变一个元素，我们可以将当前元素 `nums[i]` 减小到比下一个元素 `nums[i + 1]` 小的最小值，或者将下一个元素 `nums[i + 1]` 增大到比当前元素 `nums[i]` 大的最小值。因此，我们只需要找到这两个数中的最小值即可。

具体来说，我们可以使用 Python 内置函数 `min()` 来找到两个数中的最小值。如果这个最小值小于等于另一个数，则说明它们可以相等，即不需要进行任何操作；否则，我们需要将较小的那个数减小到等于较大的那个数。

最后，如果所有元素都满足非递减的条件，则返回 True;否则，返回 False。

三、解题方法二

另一种解决方法是使用双指针法。具体来说，我们可以定义两个指针 `left` 和 `right`,分别指向数组的开头和结尾。然后，我们从左到右遍历数组中的每个元素，并检查当前元素是否小于等于右边的元素。如果是，则说明当前元素需要被修改，以使得整个数组能够变成非递减数列。

为了只改变一个元素，我们可以将当前元素 `nums[i]` 减小到比右边的元素 `nums[j]` 小的最小值，或者将右边的元素 `nums[j]` 增大到比当前元素 `nums[i]` 大的最小值。因此，我们只需要找到这两个数中的最小值即可。

具体来说，我们可以使用双指针法来实现这个算法。首先，我们将 `left` 指针指向数组的第一个元素，将 `right` 指针指向数组的最后一个元素。然后，我们从左到右遍历数组中的每个元素 `i`,并检查当前元素是否小于等于右边的元素 `nums[j]`。如果是，则说明当前元素需要被修改，我们需要移动 `left` 指针到下一个位置，并更新左边的最小值；否则，我们需要移动 `right` 指针到前一个位置，并更新右边的最小值。最后，如果所有元素都满足非递减的条件，则返回 True;否则，返回 False。

这个算法的时间复杂度为 O(n),其中 n 为数组的长度。

def checkPossibility(nums):
    left, right = 0, len(nums) - 1
    for i in range(len(nums)):
        while left < right and nums[left] > nums[i]:
            # 如果左边的元素比当前元素大，则将左边的指针向右移动一位
            left += 1
        while left < right and nums[right] < nums[i]:
            # 如果右边的元素比当前元素小，则将右边的指针向左移动一位
            right -= 1
        if left >= right:
            # 如果左边的指针已经到达了数组的末尾，说明无法通过修改元素使得整个数组变成非递减数列
            return False
        # 将当前元素修改为左边和右边中的最小值，以满足非递减的条件
        nums[i] = min(nums[left], nums[right])
    return True