Description

给定字符串\(s\)以及常数\(k\),移除\(\mid s \mid - k\)个字符使得字典序最小

Constraints

\(\mid s \mid\)不超过\(10^5\)

Solution

单调栈秒了

Code

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        stack<int> stk;
        int max_delete = nums.size() - k;
        for(size_t i = 0; i < nums.size(); ++i) {
            while(!stk.empty() && nums[i] < stk.top() && max_delete) {
                stk.pop();
                max_delete--;
            }
            stk.push(nums[i]);
        }
        // NOTE
        while(max_delete--) stk.pop();
        vector<int> ans;
        while(!stk.empty()) {
            ans.emplace_back(stk.top());
            stk.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

LeetCode-1673 Find the Most Competitive Subsequence