求删除k个字母后的最小字典序字符串

发布时间 2023-11-16 19:44:18作者: spiderflower

  对于一个字符串来说我们要找删除k个字母后的最小字典序字符串来说,我们肯定是从前往后来删除,如果遇见前一个字母比后一个字母(字典序)大,那就删除前一个。对于此来说我们用一个vector来维护,vector就是存的答案,如果vector的最后一个字母比枚举的字母大,那就删除最后一个。

vector<char>v;
//k次数
for (int i = 0; i < s.size(); i++) {
    while (!v.empty() && v.back() > s[i] && k) {
        v.pop_back();
        k--;
    }
    v.push_back(s[i]);
}