LeetCode每日一题：找出最具竞争力的子序列

传送门

题目意思很好理解，就是维护一个单调栈。

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        int n = nums.size();
        if(k == n) return nums;
        stack<int> st;

        for(int i = 0; i < n; i++) {
            while(!st.empty() && st.top() > nums[i] && k - st.size() < n - i) {
                st.pop();
            }
            if (st.size() < k) {
                st.push(nums[i]);
            }
        }

        vector<int> ans;
        while(!st.empty()) {
            ans.push_back(st.top());
            st.pop();
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};

这么写居然还能双百，挺离谱的。后来想了想，完全不用stack

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        int n = nums.size();
        if(k == n) return nums;
        vector<int> ans;

        for(int i = 0; i < n; i++) {
            while(ans.size() != 0 && ans.back() > nums[i] && k - ans.size() < n - i) {
                ans.pop_back();
            }
            if (ans.size() < k) {
                ans.push_back(nums[i]);
            }
        }

        return ans;
    }
};