# 1673. Find the Most Competitive Subsequence
###### tags: `Leetcode` `Medium` `Stack`
Link: https://leetcode.com/problems/find-the-most-competitive-subsequence/
## 思路 $O(N)$ $O(k)$
If current element a is smaller then the last element in the stack,
we can replace it to get a smaller sequence.

Before we do this,
we need to check if we still have enough elements after.
After we pop the last element from stack,
we have $stack.size()-1$ in the stack,
there are $nums.size()-i$ can still be pushed.
if $stack.size()-1+nums.size()-i\geq k$, we can pop the stack.

Then, is the stack not full with $k$ element,
we push $nums[i]$ into the stack.

Finally we return stack as the result directly.

## Code

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<nums.length; i++){
            while(!stack.isEmpty() && nums[i]<stack.peek() && nums.length-i-1>=k-stack.size()){
                stack.pop();
            }
            if(stack.size()<k) stack.push(nums[i]);
        }
        
        int[] ans = new int[k];
        int idx = k-1;
        while(idx>=0) ans[idx--]=stack.pop();
        return ans;
    }
}