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;
}
};