很容易想到，为了确保最终每一个数字仅出现一次，我们可以对原字符串中每一个数字进行频率统计，而最终的结果字符串中每一个数字出现的频率应该为1。频率统计我们可以用我们熟知的Counter()来完成，即初始化哈希表cnt = Counter(s)。另外，我们还需要知道某一个数字是否在栈中已经出现过了，这可以用一个哈希集合used或者长度为10的列表来记录。

接着我们从左往右遍历原字符串s，然后考虑每一个字符num的行为。当

如果num没有使用过，即不位于哈希集合used中
- num可以直接****入栈的情况有
  - 栈为空
  - 栈不为空，但num小于栈顶元素stack[-1]
  - 栈不为空，且num大于栈顶元素stack[-1]，但stack[-1]的计数为1，如果stack[-1]被弹出则最终结果将不包含stack[-1]
- 如果上述条件均不满足，num不可以直接入栈，需要反复进行栈顶元素检查并弹出栈顶元素。对于弹出的元素top = stack.pop()，需要做两件事情
  - top的计数-1，即cnt[top] -= 1。
  - top要在哈希集合used中移除，因为暂时不在栈中出现了。
- num入栈之后，需要将其加入哈希集合used，表示num在栈出现了
如果num已经使用过，即已经位于哈希集合used中
- num不能入栈
- num的计数-1，即cnt[num] -= 1。

将上述思路整理成代码

for num in num_lst:
    if num in used:
        cnt[num] -= 1   
    else:
        while (len(stack) > 0 and num > stack[-1] and cnt[stack[-1]] > 1):
            cnt[stack[-1]] -= 1     
            used.remove(stack[-1])  
            stack.pop()             
        stack.append(num)
        used.add(num)

本题基本就完成了。

代码

Python

# 题目：2023Q1A-删除重复数字后的最大数字
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：单调栈
# 代码看不懂的地方，请直接在群上提问

from collections import Counter

num_lst = list(input()) # 把输入的字符串转化为字符列表，每个元素为一个数字字符
cnt = Counter(num_lst)  # 计数哈希表，记录每一个数字的出现次数
stack = list()          # 单调递减栈，更大的数字在栈底
used = set()            # 查看ch是否使用过
for num in num_lst:
    # 如果num位于used中，说明在此之前使用过了，无需入栈
    if num in used:
        cnt[num] -= 1   # cnt[ch]的计数-1
    # 如果ch不位于used中，要把ch加入栈顶
    else:
        # 在加入栈底之前，需要进行栈顶元素的检查，
        # 有可能要弹出若干栈顶元素，弹出的条件为：
        # 1.栈不为空；
        # 2.num大于栈顶元素stack[-1]
        # 3.栈顶元素的计数cnt[stack[-1]]大于1（即后面还有其他相同字符可用）
        while (len(stack) > 0 and num > stack[-1] and cnt[stack[-1]] > 1):
            cnt[stack[-1]] -= 1     # 对于栈顶弹出的元素，其计数-1
            used.remove(stack[-1])  # 同时在used集合中移除
            stack.pop()             # 栈顶元素弹出
        # 在进行完栈顶的检查之后，需要做两件事：
        # 1.把ch加入栈顶；
        # 2.把ch加入used哈希表，表示已经使用过
        stack.append(num)
        used.add(num)

# 最后需要把单调栈中的所有元素用join()方法合并成一个字符串并输出
print("".join(stack))

Java

import java.util.ArrayList;  
import java.util.HashSet;  
import java.util.LinkedList;  
import java.util.Map;  
import java.util.Set;  
  
public class Main {  
    public static void main(String[] args) {  
        // 从用户输入获取字符列表，每个元素为一个数字字符  
        String input = System.console().readLine();  
        char[] numChars = input.toCharArray();  
          
        // 计数哈希表，记录每一个数字字符的出现次数  
        Map<Character, Integer> cnt = CounterUtil.count(numChars);  
          
        // 单调递减栈，更大的数字在栈底  
        LinkedList<Character> stack = new LinkedList<>();  
          
        // 查看字符是否使用过  
        Set<Character> used = new HashSet<>();  
          
        // 遍历字符列表  
        for (char num : numChars) {  
            // 如果字符已存在于used集合中，说明已使用过，无需入栈，减少计数  
            if (used.contains(num)) {  
                cnt.put(num, cnt.get(num) - 1);  
            } else {  
                // 如果字符未存在于used集合中，加入栈顶  
                // 在加入栈顶之前，需要进行栈顶元素的检查，可能需要弹出若干栈顶元素  
                while (!stack.isEmpty() && num > stack.peekLast() && cnt.get(stack.peekLast()) > 1) {  
                    // 对于栈顶弹出的元素，减少计数，从used集合中移除，弹出栈顶元素  
                    cnt.put(stack.pollLast(), cnt.get(stack.pollLast()) - 1);  
                    used.remove(stack.pollLast());  
                }  
                // 加入栈顶元素，加入used集合  
                stack.addLast(num);  
                used.add(num);  
            }  
        }  
          
        // 最后需要把单调栈中的所有元素用join()方法合并成一个字符串并输出  
        String result = String.join("", stack);  
        System.out.println(result);  
    }  
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>

using namespace std;

int main() {
    string num_lst;
    cin >> num_lst;

    unordered_map<char, int> cnt;
    for (char ch : num_lst) {
        cnt[ch]++;
    }

    stack<char> st;
    unordered_set<char> used;
    for (char ch : num_lst) {
        if (used.find(ch) != used.end()) {
            cnt[ch]--;
        } else {
            while (!st.empty() && ch > st.top() && cnt[st.top()] > 1) {
                cnt[st.top()]--;
                used.erase(st.top());
                st.pop();
            }
            st.push(ch);
            used.insert(ch);
        }
    }

    string result;
    while (!st.empty()) {
        result = st.top() + result;
        st.pop();
    }

    cout << result << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。N是输入数字的位数。

空间复杂度：O(1)。单调栈和哈希表所占用的额外空间，长度不超过10，故可以认为是常数级别空间。