题面描述

给定一个正整数 $NUM1$，计算出一个新的正整数 $NUM2$，其中 $NUM2$ 是通过从 $NUM1$ 中移除 $N$ 位数字得到的结果，并且需要保证 $NUM2$ 的值最小。

思路

要在给定的数字字符串中移除 $N$ 位数字，使得剩下的数字组成的数尽可能小。这个问题可以通过贪心算法来解决。具体步骤如下：

1. 贪心选择：从左到右遍历数字，每当发现当前数字比下一个数字大时，就移除当前数字。这是因为移除较大的数字有助于整体数值变小。
2. 重复此过程：重复上述步骤，直到移除的数字达到 $N$ 位。
3. 处理剩余情况：如果遍历完所有数字后仍未移除足够的数字，则从数字的末尾继续移除剩余的数字。
4. 去除前导零：最后的结果可能会有前导零，需要将其去除。

代码分析

1. 使用栈结构：利用栈来保存结果数字。遍历数字字符串的每一位数字：
   • 当当前数字小于栈顶数字且还可以移除数字时，弹出栈顶数字。
   • 将当前数字压入栈中。
2. 处理剩余移除：如果遍历完后仍有剩余的移除次数，则从栈顶开始移除。
3. 构造结果：将栈中的数字按顺序组合成结果字符串，并去除前导零。
4. 边界处理：确保输入的合法性，如 $N$ 小于数字长度。

cpp

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(){
    string num;
    int k;
    // 读取输入
    cin >> num;
    cin >> k;
    
    int n = num.length();
    // 使用栈保存结果数字
    string result = "";
    int remove = k;
    
    for(char c : num){
        // 当当前数字小于结果最后一位，且还有移除机会时，弹出最后一位
        while(!result.empty() && result.back() > c && remove > 0){
            result.pop_back();
            remove--;
        }
        result += c;
    }
    // 如果还有移除次数，移除末尾
    while(remove > 0){
        result.pop_back();
        remove--;
    }
    // 去除前导零
    size_t start = 0;
    while(start < result.size()-1 && result[start] == '0') start++;
    result = result.substr(start);
    
    cout << result;
    return 0;
}

python

# 读取输入
num = input().strip()
k = int(input())

result = []
remove = k

for c in num:
    # 当当前数字小于栈顶数字，且还有移除机会时，弹出栈顶
    while result and result[-1] > c and remove > 0:
        result.pop()
        remove -= 1
    result.append(c)

# 如果还有移除次数，移除末尾
if remove > 0:
    result = result[:-remove]

# 转为字符串并去除前导零
result_str = ''.join(result).lstrip('0')

# 如果结果为空，则返回 '0'
print(result_str if result_str else '0')

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String num = sc.next();
        int k = sc.nextInt();
        
        StringBuilder result = new StringBuilder();
        int remove = k;
        
        for(char c : num.toCharArray()){
            // 当当前数字小于结果最后一位，且还有移除机会时，弹出最后一位
            while(result.length() > 0 && result.charAt(result.length()-1) > c && remove > 0){
                result.deleteCharAt(result.length()-1);
                remove--;
            }
            result.append(c);
        }
        // 如果还有移除次数，移除末尾
        while(remove > 0){
            result.deleteCharAt(result.length()-1);
            remove--;
        }
        // 去除前导零
        int start = 0;
        while(start < result.length()-1 && result.charAt(start) == '0') start++;
        String finalResult = result.substring(start);
        
        System.out.println(finalResult);
    }
}

题目描述

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

输入描述

输入的第一行为一个字符串，字符串由 $0-9$ 字符组成，记录正整数 $NUM1$，$NUM1$ 长度小于 $32$。

输入的第二行为需要移除的数字的个数，小于 $NUM1$ 长度。

输出描述

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

样例1

输入

2615371
4

输出

131

说明

NUM2可能有前导0，如果有则需要去除