在 Python 中寻找最具竞争力子序列的程序

假设我们有一个数组 nums 和另一个值 k，我们必须找到大小为 k 的 nums 中最具竞争力的子序列。如果在 s1 和 s2 不同的第一个位置，子序列 s1 的数字小于 s2 中的相应数字，则子序列 s1 比子序列 s2（大小相同）更具竞争力。

因此，如果输入类似于 nums = [4,6,3,7] k = 2，那么输出将是 [3,7]，因为在所有大小为 2 的子序列中，{[4,6], [4, 3], [4,7], [6,3], [6,7], [3,7]}，其中[3,7]最具竞争力。

示例

让我们看看以下实现以获得更好的理解 -

def solve(nums, k):
   attempts = len(nums) - k
   stack = []
   for num in nums:
      while stack and num < stack[-1] and attempts > 0:
         stack.pop()
         attempts -= 1
      stack.append(num)

   return stack[:k]

nums = [4,6,3,7]
k = 2
print(solve(nums, k))

输入

[4,6,3,7], 2

[3,7]