Python中查找最有竞争力子序列的程序

假设我们有一个数组nums和另一个值k，我们必须找到nums的大小为k的最有竞争力子序列。这里，如果在子序列s1和s2的第一个位置上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]是最有竞争力的。

为了解决这个问题，我们将按照以下步骤进行-

attempts := nums的大小 – k
stack := 一个新的列表
对于nums中的每个数字，执行以下操作
- 当stack不为空，num < 栈的顶部，尝试 > 0时，执行以下操作
  - 从stack中弹出元素
  - attempts := attempts – 1
- 将num推入stack中
返回stack的前k个元素

示例

让我们看看以下实现以更好地理解-

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))