如何优化列表操作？（CodeFights）——优化almostIncreasingSequence函数性能

我手头有个函数，在处理小列表的时候表现挺不错的——它的核心作用是检查移除序列中的任意一个元素后，该序列能否变成严格递增序列。

完整代码（补充了原代码中未写完的逻辑部分） #

def almostIncreasingSequence(sequence):
    length = len(sequence)
    for i in range(1, length):
        # 移除第i个元素生成新序列
        newSequence = sequence[:i-1] + sequence[i:]
        if checkIfSorted(newSequence):
            return True
    # 最后单独检查移除最后一个元素的情况
    return checkIfSorted(sequence[:length-1])

def checkIfSorted(sequence):
    # 遍历验证序列是否严格递增
    for i in range(1, len(sequence)):
        if sequence[i] <= sequence[i-1]:
            return False
    return True

逻辑说明 #

• 外层函数almostIncreasingSequence会逐个尝试移除序列里的元素（从第1个到倒数第2个），生成新序列后交给辅助函数验证
• 辅助函数checkIfSorted负责判断传入的序列是否满足严格递增的要求
• 只要有一次移除后的序列符合条件，就立刻返回True；如果遍历完都没找到，最后再单独检查移除最后一个元素的情况

需要注意的是，这个方法的时间复杂度是O(n²)，所以更适合小数据量的场景，处理大列表时效率会比较受限。

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