题目描述
在一个数组中找出长度k的子序列，使其字典序最小？
| f1-单调栈 |
基本分析
- 字典序最小肯定是单调不减最好，但是怎么保证序列的长度是k？需要删除的个数是n-k，利用单调栈同时维护这个信息，超过了就不再维护有序性了。
- stk中最终的结果有没有可能多于k？可能的，比如本身就是单调不减，会在stk中一直加。
代码
class Solution:
def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
stk = []
n = len(nums)
last = n - k
for i in range(n):
while stk and last and stk[-1] > nums[i]:
stk.pop()
last -= 1
stk.append(nums[i])
return stk[:k]
总结
- 利用单调栈维护前面的单调不减的特性
- 利用另一个参数保证长度为k
- stk长度可能会超过k，注意取切片