有效地从python列表中获取非递减子序列

Question

我写了一个代码来从 python 列表中获取非递减子序列lis = [3, 6, 3, 8, 6, 4, 2, 9, 5]ind = 0newlis = []while ind < len(lis):    minele = min(lis[ind:])    newlis.append(minele)    ind = lis.index(minele) + 1print(newlis)虽然它似乎与我尝试过的测试用例一起工作得很好，但有没有更有效的方法来做到这一点，因为对于列表已经排序的情况，这段代码的最坏转换时间复杂度是 O(n^2)，假设内置的 min 方法使用线性搜索。更准确地说，我想要最长的非递减子列表，并且子列表应该从列表的最小元素开始。并且通过子列表，我的意思是元素不需要在给定的原始列表（lis）中连续延伸。

Answer 1

我几乎确信它可以在线性时间内运行。您只需要在一次扫描期间继续尝试构建最长的序列，然后像我一样将它们全部存储或保留当前最长的序列。

lis = [9, 1, 3, 8, 9, 6, 9, 8, 2, 3, 4, 5]

newlis = [[]]

minele = min(lis)

ind = lis.index(minele)

currmin = minele

seq = 0

longest = 0

longest_idx = None

while ind < len(lis):

    if lis[ind] >= currmin:

        newlis[seq].append(lis[ind])

        currmin = lis[ind]

        ind += 1

    else:

        if len(newlis[seq]) > longest:

            longest = len(newlis[seq])

            longest_idx = seq

        newlis.append([minele])

        currmin = minele

        seq += 1

if len(newlis[seq]) > longest:

    longest = len(newlis[seq])

    longest_idx = seq

print(newlis)

print(newlis[longest_idx])