解题思路

这道题要求找出字典序最大的子序列，关键点是：

  1. 子序列不要求连续，但要保持原有顺序
  2. 需要找出字典序最大的子序列
  3. 可以删除任意数量的字符（包括全部删除或不删除）

解题步骤：

  1. 从后向前遍历字符串
  2. 维护一个当前见过的最大字符
  3. 如果当前字符大于等于已见过的最大字符，则选择该字符
  4. 这样可以保证得到字典序最大的子序列

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    
    string result;
    char maxChar = 'a' - 1;  // 初始化为比'a'小的字符
    
    // 从后向前遍历
    for(int i = s.length() - 1; i >= 0; i--) {
        if(s[i] >= maxChar) {
            result = s[i] + result;  // 在结果前面添加当前字符
            maxChar = s[i];  // 更新最大字符
        }
    }
    
    cout << result << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        StringBuilder result = new StringBuilder();
        char maxChar = (char)('a' - 1);  // 初始化为比'a'小的字符
        
        // 从后向前遍历
        for(int i = s.length() - 1; i >= 0; i--) {
            if(s.charAt(i) >= maxChar) {
                result.insert(0, s.charAt(i));  // 在结果前面添加当前字符
                maxChar = s.charAt(i);  // 更新最大字符
            }
        }
        
        System.out.println(result.toString());
    }
}

s = input()
result = []
max_char = chr(ord('a') - 1)  # 初始化为比'a'小的字符

# 从后向前遍历
for c in reversed(s):
    if c >= max_char:
        result.insert(0, c)  # 在结果前面添加当前字符
        max_char = c  # 更新最大字符

print(''.join(result))

算法及复杂度

  • 算法：贪心算法。从后向前遍历，保留所有不小于已见过的最大字符的字符。
  • 时间复杂度：，其中n是字符串长度。
  • 空间复杂度：，需要存储结果字符串。