如何减少列表遍历器的执行时间限制

Question

我正在处理Code Signal上的Python问题，我试图查看给定的列表是否在仅从中删除一个元素时是严格递增的序列。因此，我构建了一些代码，在 for 循环中，从列表中删除元素并检查它是否是递增序列，然后在该确切索引处替换该元素并重新开始。这是代码：idef almostIncreasingSequence(sequence):    for i in range(len(sequence)):        element = sequence[i]        del sequence[i]        if all(i < j for i, j in zip(sequence, sequence[1:])):            return True        sequence.insert(i, element)    return False代码运行良好，但它会导致执行时间错误。有没有办法改进这个现有的代码，让它运行得更快？

Answer 1

浏览列表会更快，将每个值与前一个值进行比较，以确保它严格增加。对于列表中的一个数字，允许此错误，并跳过此数字。不幸的是，这并不是那么简单，正如我们在下面看到的那样：

不起作用（例如。[1,4,2,3])

def almostIncreasingSequence(sequence):

    lastValue = sequence[0]

    removed_value = False

    for i in range(1,len(sequence)):

        if sequence[i] <= lastValue:

            if removed_value:

                return False

            else:

                removed_value = True

        else:

            lastValue = sequence[i]

    return True

相反，如果我们遇到非增加，我们需要涵盖两种可能性：删除当前数字（例如。[1，2，1，3]）或删除前一个（例如。[1，2，8，4]）。我们还有一些边缘情况用于删除列表中的第一个或最后一个数字。

最终（不那么漂亮）的解决方案

def almostIncreasingSequence(sequence):

    lastValue = sequence[0]

    skipped_value = False

    for i in range(1,len(sequence)):

        if sequence[i] <= lastValue:

            if i+1 == len(sequence):

                return not skipped_value # last number is not decreasing, skip if we can

            if skipped_value: 

                # if we've already skipped a number - won't work

                return False

            elif sequence[i+1] > sequence[i-1]:

                # skipping the current number will fix it

                skipped_value = True

                lastValue = sequence[i-1]

            else:

                # try and skip the previous number

                skipped_value = True

                if i == 1 or sequence[i] > sequence[i-2]:

                    # can skip the previous number and it'll work

                    lastValue = sequence[i]

                else:

                    # we have no chance

                    return False  

        else:

            lastValue = sequence[i]

    return True