题目描述与示例

题目

一个长整型数字，消除重复的数字后，得到最大的一个数字。

如 12341 ，消除重复的 1，可得到 1234 或 2341，取最大值 2341。

如 42234，消除 4 得到 4223 或者 2234 ，再消除 2，得到 423 或 234，取最大值 423。

输入

输入一个数字，范围 [1, 100000]

输出

输出经过删除操作后的最大值

示例一

输入

12341

输出

2341

示例二

输入

42234

输出

423

解题思路

注意，本题和LC316. 去除重复字母非常类似。区别在于，本题字符串包含的是数字而不是字母，需要考虑最大数字而不是最小数字。

为了使得最终结果尽可能大，较大的单个数字自然是尽可能地排在前面。这似乎很直接地就可以使用单调栈的思路来完成：设置一个从栈底往栈顶递减的单调栈。

使用单调栈，一种朴素美好的设想是：每遇到一个数num，就与栈顶元素stack[-1]进行比较，如果num比stack[-1]大，那么若干比num小的栈顶元素可能会被删除。

但由于最终删除后的结果必须是，原字符串中的单个数字有且只出现一次，故本题还需要考虑几个问题：

  1. 如何确保重复出现的数字被删除
  2. 如何确保每一个数字最终只出现一次

很容易想到，为了确保最终每一个数字仅出现一次，我们可以对原字符串中每一个数字进行频率统计，而最终的结果字符串中每一个数字出现的频率应该为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++

“`C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>

using namespace std;

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

<pre><code>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;
</code></pre>

}

“`

时空复杂度

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

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

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）

上一篇 【单调栈】2023C-找朋友
下一篇 【单调栈】2023C-找最小数

相关文章