删除一个元素使数组严格递增

难度: Easy

给你一个下标从 0 开始的整数数组 nums ，如果恰好删除一个元素后，数组 严格递增 ，那么请你返回 true ，否则返回 false 。如果数组本身已经是严格递增的，请你也返回 true 。

数组 nums 是 严格递增 的定义为：对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i] 。

示例 1：

输入：nums = [1,2,10,5,7]
输出：true
解释：从 nums 中删除下标 2 处的 10 ，得到 [1,2,5,7] 。
[1,2,5,7] 是严格递增的，所以返回 true 。

示例 2：

输入：nums = [2,3,1,2]
输出：false
解释：
[3,1,2] 是删除下标 0 处元素后得到的结果。
[2,1,2] 是删除下标 1 处元素后得到的结果。
[2,3,2] 是删除下标 2 处元素后得到的结果。
[2,3,1] 是删除下标 3 处元素后得到的结果。
没有任何结果数组是严格递增的，所以返回 false 。

示例 3：

输入：nums = [1,1,1]
输出：false
解释：删除任意元素后的结果都是 [1,1] 。
[1,1] 不是严格递增的，所以返回 false 。

示例 4：

输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 已经是严格递增的，所以返回 true 。

提示：

2 <= nums.length <= 1000
1 <= nums[i] <= 1000

Submission

运行时间: 20 ms

内存: 16.6 MB

def isIncreasing(a):
    return all(b < c for b, c in zip(a, a[1:]))

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        for i in range(len(nums)-1):
            if nums[i] >= nums[i+1]:
                if not isIncreasing(nums[i+2:]):
                    return False
                if i+2 >= len(nums) or nums[i] < nums[i+2]:
                    return True
                if nums[i+1] >= nums[i+2]:
                    return False
                return i-1 < 0 or nums[i-1] < nums[i+1]
        return True

Explain

题解采用了一种迭代的方式来确定是否可以通过删除一个元素使数组变成严格递增的。主要步骤包括：1) 遍历数组，寻找违反严格递增规则的相邻元素对(nums[i] >= nums[i+1])。2) 当找到这样的元素对时，尝试删除 nums[i] 或 nums[i+1]，并检查剩余部分是否严格递增。3) 如果删除 nums[i+1] 后 nums[i+2:] 是严格递增的，并且 nums[i] < nums[i+2] 或 nums[i] 是数组的第一个元素，则返回true。4) 如果删除 nums[i] 后 nums[i+1:] 是严格递增的，并且 nums[i-1] < nums[i+1] 或 nums[i+1] 是数组的第一个元素，则返回true。5) 如果数组本身是严格递增的，也直接返回true。

时间复杂度: O(n)

空间复杂度: O(1)

def isIncreasing(a):
    # 判断数组 a 是否严格递增
    return all(b < c for b, c in zip(a, a[1:]))

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        for i in range(len(nums)-1):
            if nums[i] >= nums[i+1]:
                # 检查去除 nums[i+1] 后，剩余数组是否严格递增
                if not isIncreasing(nums[i+2:]):
                    return False
                # 检查 nums[i] 与 nums[i+2] 的关系
                if i+2 >= len(nums) or nums[i] < nums[i+2]:
                    return True
                # 检查 nums[i+1] 与 nums[i+2] 的关系
                if nums[i+1] >= nums[i+2]:
                    return False
                # 检查 nums[i-1] 与 nums[i+1] 的关系
                return i-1 < 0 or nums[i-1] < nums[i+1]
        return True # 如果数组已经是严格递增的

Explore

题解中实现检查数组是否严格递增的方法是通过一个辅助函数 `isIncreasing(a)`。这个函数使用 Python 的 `zip` 函数和列表推导式来比较数组中的每个元素与其后继元素。具体实现为：`all(b < c for b, c in zip(a, a[1:]))`，这里 `zip(a, a[1:])` 会生成一个包含相邻元素对的迭代器，然后对于每对元素 (b, c)，检查 b 是否小于 c。如果所有相邻元素对都满足这一条件，函数返回 `True`，表示数组是严格递增的；否则返回 `False`。

题解中的策略是在发现第一个违反递增规则的元素对 `nums[i] >= nums[i+1]` 后，尝试通过删除一个元素来使数组恢复严格递增的状态。这种方法基于的假设是，如果可以通过删除一个元素使数组变为严格递增，则最多只会有一处违反严格递增的情况。如果在尝试删除一个元素之后，数组仍然不能变为严格递增，或者在尝试删除后发现删除的方法不符合条件（如删除后的元素仍然不满足严格递增），则直接返回 `False`。这样做可以避免不必要的后续检查，提高算法效率。

在决定删除 `nums[i]` 或 `nums[i+1]` 时，题解中采用的策略是尝试两种可能的删除方式，并检查哪种方式可以使得剩余数组严格递增。首先尝试删除 `nums[i+1]`，并检查剩余部分 `nums[i+2:]` 是否严格递增，并确保 `nums[i] < nums[i+2]`（如果 `i+2` 在数组范围内）。如果这种方式失败，即 `nums[i+1]` 删除后数组不严格递增或 `nums[i] >= nums[i+2]`，则尝试删除 `nums[i]`，并检查剩余部分 `nums[i+1:]` 是否严格递增，且 `nums[i-1] < nums[i+1]`（如果 `i-1` 在数组范围内）。这种动态的检查方式允许算法根据具体情况灵活决定删除哪个元素，从而增加成功使数组严格递增的可能性。