Skip to content

Latest commit

 

History

History
 
 

1673.Find-the-Most-Competitive-Subsequence

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1673.Find-the-Most-Competitive-Subsequence

本题和LC.402 Remove K Digits一模一样,本质上就是求长度为k的最小序列。

我们维护一个递增的栈,一旦发现新数字a比栈顶元素b更小,我们肯定希望把这个a尽量前移(这样必然使得序列更小)。把a每前移一位,就意味着要舍弃栈顶的数字,直至已经被舍弃的数字总数达到上限。

当所有数字都入了栈,那么栈里面的就是最小的递增序列。当然,如果这个序列的数字数目大于了k,那么就舍弃最后的数字舍得剩下的恰好有k个。