如何判断移除至多一个元素后数组能否成为严格递增序列？

核心思路 #

遍历数组时，一旦遇到不满足严格递增的位置（即nums[i] <= nums[i-1]），我们需要尝试移除当前元素或前一个元素，同时记录移除次数。如果移除次数超过1，直接判定为不可行；否则调整数组状态（模拟移除操作），继续遍历后续元素。

具体步骤 #

• 初始化remove_count为0，用于统计移除元素的次数。
• 从索引1开始遍历数组：
  1. 若nums[i] <= nums[i-1]，说明出现递减，remove_count加1。
  2. 若remove_count > 1，直接返回false，因为已超过至多移除一个元素的限制。
  3. 判断需要移除哪个元素：
     • 如果i > 1且nums[i] <= nums[i-2]：此时移除当前元素无法让后续序列递增（比如[3,4,2,3]中，2既小于4也小于3），必须移除前一个元素，因此将nums[i-1]赋值为nums[i]，模拟移除前一个元素的效果，方便后续比较。
     • 否则：移除当前元素即可满足局部递增，将nums[i]赋值为nums[i-1]，模拟移除当前元素的效果。
• 遍历完成后返回true。

代码实现（Python） #

def can_be_increasing(nums):
    remove_count = 0
    for i in range(1, len(nums)):
        if nums[i] <= nums[i-1]:
            remove_count += 1
            if remove_count > 1:
                return False
            # 决定移除当前元素还是前一个元素
            if i > 1 and nums[i] <= nums[i-2]:
                nums[i-1] = nums[i]
            else:
                nums[i] = nums[i-1]
    return True

测试用例验证 #

• [1,2,3] → 返回True（无需移除）
• [1,3,2] → 返回True（移除3或2均可）
• [3,2,1] → 返回False（需移除两个元素）
• [1,4,2,3] → 返回True（移除4后序列为[1,2,3]）
• [3,4,2,3] → 返回False（无论移除4还是2，剩余序列仍不严格递增）

内容的提问来源于stack exchange，提问作者Sahil