寻求非迭代式数组严格递增验证优化方案（适配大数据量）

我写了一种解法，但处理超大输入时性能拉胯，过不了测试。有没有不用暴力迭代的实现方式？

挑战说明 #

给定整数数组形式的序列，判断是否可以通过移除至多一个元素得到严格递增序列。
注：序列a₀, a₁, ..., aₙ满足a₀ < a₁ < ... < aₙ则视为严格递增，仅含单个元素的序列也视为严格递增。

示例 #

• 当sequence = [1, 3, 2, 1]，输出应为solution(sequence) = false——没法通过移除一个元素得到严格递增序列。
• 当sequence = [1, 3, 2]，输出应为solution(sequence) = true——可以移除3得到[1,2]，或移除2得到[1,3]。

输入输出约束 #

• [执行时间限制] 4秒（Python3）
• [输入] array.integer sequence
  约束条件：2 ≤ sequence.length ≤ 10⁵，-10⁵ ≤ sequence[i] ≤ 10⁵
• [输出] boolean
  返回是否可通过移除至多一个元素得到严格递增序列。

现有低效解法 #

def solution(sequence):
    for number in range(len(sequence)):
        shortened = sequence.copy()
        shortened.pop(number)
        if len(shortened) == len(set(shortened)):
            if shortened == sorted(shortened):
                return True
    return False

优化方案 #

你的现有解法问题在于暴力枚举每个元素移除后的场景，每次都要拷贝数组、转集合、排序，时间复杂度是O(n² log n)，面对10⁵级别的输入必然超时。根本不需要暴力迭代每个移除情况，一次遍历就能解决：

核心思路：遍历序列时记录不符合严格递增的次数，同时判断移除当前元素还是前一个元素能让序列恢复递增，最多允许一次这样的修正。

优化后的代码：

def solution(sequence):
    count = 0
    n = len(sequence)
    for i in range(1, n):
        if sequence[i] <= sequence[i-1]:
            count += 1
            # 超过一次不符合，直接返回False
            if count > 1:
                return False
            # 判断移除哪个元素能恢复递增
            if i == 1 or sequence[i] > sequence[i-2]:
                # 移除前一个元素，修改前一个值以便后续比较
                sequence[i-1] = sequence[i]
            else:
                # 移除当前元素，修改当前值以便后续比较
                sequence[i] = sequence[i-1]
    return True

代码解释 #

1. 用count记录不符合严格递增的次数，最多允许1次。
2. 从第二个元素开始遍历：
   • 发现当前元素<=前一个元素时，计数加1，超过1次直接返回False。
   • 然后判断修正方式：
     • 如果是第一次出现不符合（i=1），或者当前元素比前前一个元素大，说明移除前一个元素就能让序列恢复递增，所以修改前一个元素的值为当前元素（后续比较时相当于忽略了原前一个元素）。
     • 否则，说明必须移除当前元素，修改当前元素的值为前一个元素（后续比较时相当于忽略了当前元素）。
3. 遍历完成后返回True，说明最多只需要移除一个元素就能得到严格递增序列。

这个解法的时间复杂度是O(n)，空间复杂度是O(1)，完全能处理10⁵级别的输入。

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