Description

Submission

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        int count = nums.size() - k;

        stack<int> Stack;

        for(int n: nums) {
            while(count > 0 && !Stack.empty() && Stack.top() > n) {
                // cout << "pop: " << Stack.top() << endl;
                Stack.pop();
                count--;
            }

            Stack.push(n);
            // cout << "push: " << n << endl;
        }

        vector<int> rets;

        for(int i = 0; i < count; ++i) {
            Stack.pop();
        }

        while(!Stack.empty()) {
            rets.push_back(Stack.top());
            Stack.pop();
        }

        reverse(rets.begin(), rets.end());

        return rets;
    }
};

Contest Submission

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        stack<pair<int, int>> s;
        
        vector<pair<int, int>> order;
        for(int i = 0; i < nums.size(); ++i) {
            int num = nums[i];
            if(s.empty()) s.push({num, i});
            else {
                while(!s.empty() && s.top().first > num) {
                    order.push_back(s.top());
                    s.pop();
                }
                s.push({num,i});
            }
        }
        
        while(!s.empty()) {
            order.push_back(s.top());
            s.pop();
        }

        vector<pair<int,int>> ret {order.end() - k, order.end()};
        sort(ret.begin(), ret.end(), [](pair<int,int>& a, pair<int,int>& b) {
            return a.second < b.second;
        });
        vector<int> rets;
        
        for(int i = 0; i < ret.size(); ++i) {
            rets.push_back(ret[i].first);
        }
        return rets;
    }
};