严格递增子序列的最小数量

Question

问题陈述

阿德里安是一名跑步者，每天早上他都会和朋友一起去跑步。每天早上，他们的教练都会给他们一份从左到右到覆盖的检查站清单。每个检查点都有一个特殊的值。现在，教练有一个规则，即跑步者只会去值严格高于前一个检查点的检查点。此外，所有跑步者都应该严格向右移动。您需要找出覆盖所有检查点所需的最少跑步者人数。

输入采用数组的形式，从左到右表示检查点的值。

样本输入

[12, 15, 18, 17, 20, 25, 27, 19, 20, 21]

样本输出

2

案例说明：

第一名将覆盖 [12, 15, 18, 19, 20, 21]，第二名将覆盖 [17, 25, 27]。

我的代码

我的递归算法给出了正确的输出，但效率不够高。

visited = [0] * len(A)
def ans(A, visited):
    n = len(A)
    if visited.count(0) == 0:
        return 0
    num = 0
    ind = visited.index(0)
    visited[ind] = 1
    min_num = A[ind]
    for i in range(ind, n):
        if A[i] > min_num and visited[i] == 0:
            visited[i] = 1
            min_num = A[i]
    return 1 + ans(A, visited)  

题

有什么方法可以更有效地解决这个问题？我的代码在一些测试用例上给出了 TLE。我不知道如何让它工作。

我的代码给出了正确的输出。它只是不够有效。

Answer 1

您的算法的时间复杂度为O(n²)。

您可以使用以下O(nlogn)算法：

创建一个空列表，它将为每个需要的跑步者获得一个值（到目前为止）。对于每个跑步者，您将存储相应跑步者将访问的最大值（到目前为止），并且这些值（一旦他们进入那里）将按降序排列（不变）。

通过输入一次。对于每个访问过的值v，在上面提到的列表中执行二分搜索以找到小于它的最大值w。如果找到，用v覆盖那个w（即相应的 runner 将访问它）。如果未找到，则将v附加到该列表中：这意味着需要一个额外的跑步者。当然，处理第一个输入值时就是这种情况。

在此过程结束时，新列表的长度代表答案（所需的最小跑步者数量）。

执行

对于二分搜索，我将使用bisect，但您当然可以实现自己的。

由于bisect仅适用于按升序排列的列表，因此我将以相反的顺序访问A中的元素，并将跑步者的信息更新为迄今为止的最小值——因为我们正朝着相反的方向工作：

def ans(A):
    runners = []
    for val in reversed(A):
        i = bisect.bisect_left(runners, val + 1)
        if i >= len(runners):
            runners.append(val)
        else:
            runners[i] = val
    return len(runners)

注意：val + 1需要正确处理相等的值（我假设是整数）。在有重复值的情况下，这意味着同一个运行器不能访问它，所以我们应该寻找一个至少值为 的运行器val + 1（再次：我们在这里反向工作）。