找最小数 - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

给一个正整数NUM1，计算出新正整数NUM2，NUM2为NUM1中移除N位数字后的结果需要使得NUM2的值最小。

输入描述

1. 输入的第一行为一个字符串，字符串由0-9字符组成，记录正整数NUM1，NUM1长度小于32。
2. 输入的第二行为需要移除的数字的个数，小于NUM1长度。

输出描述

输出一个数字字符串，记录最小值NUM2。

示例1

输入：
2615371
4

输出：
131

说明：

示例2

输入：

输出：

说明：

题解

问题分析

这道题可以归类为贪心算法。目标是在尽量靠左的地方删除比后面大的数字，使得剩下的数字更小。删除操作中优先考虑移除高位的数字，尽量保持低位数字小。

解题的基本思路：

1. 使用一个栈来存储字符。
2. 从左到右遍历数字字符串，如果当前数字比栈顶的数字小且还可以删除数字，就弹出栈顶数字。
3. 遍历完成后，如果删除的数字还不够，则继续从后向前删除栈顶数字。
4. 最后，将栈中剩下的数字拼接成结果，并移除前导零。

时间复杂度

• 时间复杂度为O(n)，因为每个数字最多进出栈一次。
• 空间复杂度为O(n)，用于存储栈中的数字。

Java

import java.util.Scanner;
import java.util.Stack;
/**
 * @author code5bug
 */
public class Main {
    public static String removeDigits(String num, int k) {
        Stack<Character> stack = new Stack<>();
        
        for (char digit : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peek() > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }
        
        // 如果 k 还大于 0，继续从栈顶删除
        while (k > 0) {
            stack.pop();
            k--;
        }
        
        // 构建结果
        StringBuilder result = new StringBuilder();
        for (char digit : stack) {
            if (!(result.length() == 0 &&