严格递增子序列的最小数量
Minimum number of strictly increasing subsequences
问题陈述
Adrian is a runner and every morning he goes for a run with his friends.
Every morning, their coach gives them a list of checkpoints from left
to right to cover. Each checkpoint has a special value. Now, the coach
has a rule such that a runner will only go to checkpoints whose value
is strictly higher than the previous checkpoints. Also, all runners
are supposed to move strictly towards the right. You need to find out
the minimum number of runners it would take to cover all the
checkpoints.
The input is taken in the form of an array which denotes the values of
checkpoints from left to right.
Sample Input
[12, 15, 18, 17, 20, 25, 27, 19, 20, 21]
Sample Output
2
Explanation of the Sample Case:
First runner will cover [12, 15, 18, 19, 20, 21] and the second runner
will cover [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。我不知道如何让它发挥作用。
我的代码给出了正确的输出。就是效率不够。
您的算法的时间复杂度为 O(n²)。
您可以使用以下 O(nlogn) 算法：
创建一个空列表，它将为每个所需的跑步者获得一个值（到目前为止）。对于每个跑步者，您将存储相应跑步者将访问的最大值（到目前为止），并且这些值（一旦到达那里）将按降序排列（不变）。
输入一遍。对于每个访问值 v，在上述列表中执行二分查找，以找到小于它的最大值 w。如果找到，用 v 覆盖 w （即相应的跑步者将访问它）。如果未找到，则将 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 值的跑步者（同样：我们在这里向后工作）。
问题陈述
Adrian is a runner and every morning he goes for a run with his friends. Every morning, their coach gives them a list of checkpoints from left to right to cover. Each checkpoint has a special value. Now, the coach has a rule such that a runner will only go to checkpoints whose value is strictly higher than the previous checkpoints. Also, all runners are supposed to move strictly towards the right. You need to find out the minimum number of runners it would take to cover all the checkpoints.
The input is taken in the form of an array which denotes the values of checkpoints from left to right.
Sample Input
[12, 15, 18, 17, 20, 25, 27, 19, 20, 21]Sample Output
2Explanation of the Sample Case:
First runner will cover [12, 15, 18, 19, 20, 21] and the second runner will cover [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。我不知道如何让它发挥作用。
我的代码给出了正确的输出。就是效率不够。
您的算法的时间复杂度为 O(n²)。
您可以使用以下 O(nlogn) 算法：
创建一个空列表，它将为每个所需的跑步者获得一个值（到目前为止）。对于每个跑步者，您将存储相应跑步者将访问的最大值（到目前为止），并且这些值（一旦到达那里）将按降序排列（不变）。
输入一遍。对于每个访问值 v，在上述列表中执行二分查找，以找到小于它的最大值 w。如果找到，用 v 覆盖 w （即相应的跑步者将访问它）。如果未找到，则将 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 值的跑步者（同样：我们在这里向后工作）。