【华为OD-E卷 - 114 找最小数 100分（python、java、c++、js、c）】
【华为OD-E卷 - 找最小数 100分（python、java、c++、js、c）】
题目
给一个正整数NUM1，计算出新正整数NUM2，NUM2为NUM1中移除N位数字后的结果，需要使得NUM2的值最小
输入描述
- 输入的第一行为一个字符串，字符串由0-9字符组成，记录正整数NUM1，NUM1长度小于32。 输入的第二行为需要移除的数字的个数，小于NUM1长度
输出描述
- 输出一个数字字符串，记录最小值NUM2
用例
用例一：
输入：
2615371
4
输出：
131
python解法
- 解题思路：
- 要删除给定数字字符串中的k个字符，使得剩下的数字最小，可以采用贪心算法。具体步骤如下：
维护一个栈：用于构建最终结果，确保每次添加的数字尽可能小。
遍历每个字符：对于当前字符，若栈顶元素比它大且还有删除次数(k > 0)，则弹出栈顶元素，直到不再满足条件。这样可以保证高位尽可能小。
处理剩余删除次数：遍历完成后，若仍有删除次数未使用，则从末尾删除剩余次数对应的字符。
去除前导零：最终结果可能存在前导零，需去除。若结果为空，返回’0’。
def minimize_number(num, k):
# 最终需要保留的长度
length = len(num) - k
stack = []
for digit in num:
# 当栈不为空，且还有删除次数，且栈顶数字大于当前数字时，弹出栈顶
while stack and k and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# 截取前length个字符（处理剩余k的情况）
result = ''.join(stack[:length])
# 去除前导零，若结果为空则返回'0'
return result.lstrip('0') or '0'
num = input()
k = int(input())
print(minimize_number(num, k))
java解法
- 解题思路
- 使用栈模拟单调递增序列
遍历 num 的字符时，使用一个字符数组 result 来存储最终保留的数字。这个数组类似于一个单调递增栈，我们尝试让栈顶元素尽可能小。
移除较大的数字
在遍历 num 时，如果当前字符比 result 的栈顶元素小，并且还可以删除数字（toRemove > 0），那么就弹出栈顶元素（减少 toRemove 的值），从而让剩下的数字形成更小的值。
控制最终结果的长度
最终需要保留 keepLength = num.length() - toRemove 个字符，因此 result 数组的长度设为 keepLength，只允许存入 keepLength 个字符。
去除前导零
由于可能会出现前导 0，如 “10200” 移除 1 个字符后可能变成 “0200”，所以要去掉前导 0，如果去掉后字符串为空，则返回 “0”。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String num = sc.next(); // 输入的数字字符串
int toRemove = sc.nextInt(); // 需要移除的数字个数
System.out.println(findSmallest(num, toRemove));
}
private static String findSmallest(String num, int toRemove) {
// 如果需要移除的个数等于字符串长度，则返回 "0"
if (num.length() == toRemove) return "0";
int keepLength = num.length() - toRemove; // 需要保留的字符数
char[] result = new char[keepLength]; // 结果数组（模拟栈）
int pos = -1; // 当前存入 result 数组的最后一个元素位置（栈顶指针）
for (char ch : num.toCharArray()) { // 遍历字符串中的每个字符
// 维护单调递增栈：如果当前字符比栈顶元素小，并且还有删除名额，就弹出栈顶元素
while (pos >= 0 && toRemove > 0 && result[pos] > ch) {
pos--; // 退栈
toRemove--; // 还需要删除的个数减少
}
// 只有在栈的长度不超过目标长度时，才将当前字符加入
if (pos + 1 < keepLength) {
result[++pos] = ch; // 入栈
} else {
// 如果栈已满，则直接减少 toRemove 计数
toRemove--;
}
}
// 去除前导零
int start = 0;
while (start < keepLength && result[start] == '0') start++;
// 如果最终所有的数字都是 0，则返回 "0"
return start == keepLength ? "0" : new String(result, start, keepLength - start);
}
}
C++解法
- 解题思路
- 本题的目标是从一个数字字符串 num1 中移除 removeCount 个数字，使得剩下的数字形成的最小值。核心思想是使用单调递增栈，具体步骤如下：
利用双端队列（deque）作为单调递增栈
遍历 num1 的字符：
如果当前字符比 stack（单调递增栈）的栈顶元素小，并且仍然可以删除数字，就弹出栈顶元素（删除较大的数）。
这样可以确保数字整体变小。
将当前字符压入栈。
确保栈的长度符合要求
遍历结束后，如果 stack 仍然比需要保留的长度长，就继续弹出末尾元素。
去除前导零
由于可能会出现 000123 这样的情况，需要去掉前导零。
只要栈的第一个元素是 0 且长度大于 1，就不断弹出前面的 0。
返回最终的最小数字
将 stack 转换成字符串并返回。
#include <iostream>
#include <deque>
#include <string>
using namespace std;
// 获取移除指定个数后的最小数
string getResult(string num1, int removeCount) {
// 如果需要移除的字符等于字符串长度，返回 "0"
if (num1.length() == removeCount) return "0";
int remainCount = num1.length() - removeCount; // 需要保留的字符数
deque<char> stack; // 使用双端队列作为栈
// 遍历整个字符串
for (int i = 0; i < num1.length(); i++) {
// 当栈非空、仍可以删除字符、栈顶元素大于当前字符时，弹出栈顶元素（保证剩下的数字尽可能小）
while (!stack.empty() && removeCount > 0 && stack.back() > num1[i]) {
stack.pop_back(); // 删除较大的字符
removeCount--; // 递减待删除字符数
}
// 将当前字符压入栈
stack.push_back(num1[i]);
}
// 若栈中元素仍然超出需要保留的个数，弹出多余的元素
while (stack.size() > remainCount) {
stack.pop_back();
}
// 去除前导零
while (stack.front() == '0' && stack.size() > 1) {
stack.pop_front();
}
// 将双端队列转换为字符串
string result(stack.begin(), stack.end());
return result;
}
int main() {
string num1;
int count;
getline(cin, num1); // 读取字符串
cin >> count; // 读取要删除的字符个数
cout << getResult(num1, count) << endl; // 输出结果
return 0;
}
C解法
更新中
JS解法
更新中
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏