1. 问题描述：
给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具竞争力的 nums 子序列。数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。
示例 1：
输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。
示例 2：
输入：nums = [2,4,3,3,5,4,9,6], k = 4
输出：[2,3,3,4]
提示：
1 <= nums.length <= 10^50 <= nums[i] <= 10^91 <= k <= nums.length
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-most-competitive-subsequence
2. 思路分析：
① 分析题目可以知道，我们需要在给出的nums数组中找出长度为k的字典序最小的子序列，题目很好理解比较容易想到的是暴力破解，依次在nums数组中枚举长度为k的子序列然后找出字典序最小的那个但是数据规模太大了是没有办法通过的，其实这道题目考察的是栈的知识，通过栈我们可以存储数组中长度为k的字典序最小的子序列（单调栈），我们需要做的是在遍历nums数组的时候维护一个长度为k的递增的子序列，这样字典序就是最小的，实现起来也比较容易，我们在遍历的时候可以依次比较栈顶元素与遍历元素的大小关系，当发现当前遍历的元素小于栈顶元素的时候这个时候如果将元素加入栈中是逆序的，那么这个时候可能需要弹出栈顶元素（有可能是不弹出元素的），并且因为我们需要维护长度为k的子序列所以我们需要在能够构成长度为k的子序列的前提下才弹出栈顶元素，我们可以判断栈中元素的个数与nums数组中剩下未遍历的元素的数目是否是大于k的，如果满足这个条件说明构成的子序列的长度才是大于k的这个时候弹出栈顶元素才是有意义的
② 除了①中判断是否可以弹出栈顶元素的方法之外，我们还可以这样想，因为所有元素是需要入栈的所以我们在栈中弹出的元素的数目为p = len(nums) - k，所以只有在p > 0的条件下才可以弹出栈顶元素，并且我们在弹出元素的时候p应该自减，这样在遍历nums数组的时候就可以维护长度为k的字典序最小的子序列，最终我们还需要检查p是否大于0，如果大于0那么还需要弹出剩余的元素这样栈中元素的数目才是k（因为有可能nums数组是递增的这个时候栈是没有弹出一个元素）
③ 对于单调栈的题目大部分代码都是类似的只是有的细节处理不一样
3. 代码如下：
from typing import List
class Solution:
def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
stack, l = list(), len(nums)
for i in range(len(nums)):
# 能够构成长度为k的子序列才弹出栈顶元素
while stack and len(stack) + l - i > k and stack[-1] > nums[i]:
stack.pop()
stack.append(nums[i])
while len(stack) > k:
stack.pop()
return stackfrom typing import List
class Solution:
def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
# python中的列表是可以模拟栈的功能的
stack = list()
# 弹出的元素数目是len(nums) - k
p = len(nums) - k
for i in range(len(nums)):
while stack and p > 0 and stack[-1] > nums[i]:
stack.pop()
p -= 1
stack.append(nums[i])
# 当p大于0的时候说明栈中元素数目是大于k的这个时候需要弹出p个元素
for i in range(p):
stack.pop()
return stack