题解 | #BD12 最大子序列#(模拟)

解题思路

1.根据题意模拟,字符串s每增加一个元素算出其最大字典序子序列,新增元素与ans中元素对比,寻找s[i]第一次大于ans[j]的位置,新的ans等于ans.substr(0, j) + s[i];

代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    string s;
    while(cin >> s){
        string ans;
        ans += s[0];
        for(int i = 1; i < s.size(); i++){ //模拟寻找最大字典序子序列过程
            int j = 0;
            for(; j < ans.size(); j++){ //寻找s[i]第一次大于ans[j]的位置
                if(s[i] > ans[j]) break;
            }
            ans = ans.substr(0, j) + s[i]; //每增加一个元素生成对应的最大字典序子序列
        }
        cout << ans << endl;
    }
    return 0;
}

逆序遍历,遇到比目标字符小的字符将其删除

#include <bits/stdc++.h>

using namespace std;

int main(){
    string s;
    while(cin >> s){
        string ans;
        unordered_set<int> st; //保存需要删除的字符位置
        int n = s.size();
        char t = s[n-1];
        for(int i = n - 2; i >= 0; i--){ //逆序遍历
            if(s[i] >= t){
                t = s[i];
            }
            else{　//小于t的字符需要删除,以保证留下的字符串为字典序最大序列
                st.insert(i);
            }
        }
        for(int i = 0; i < n; i++){
            if(st.count(i) == 0) ans += s[i];
        }
        cout << ans << endl;
    }
    return 0;
}