好久没更新了，不是忘记了，而是做不出来。。。。。。
今天带来的是《找最小数》，话不多说，先上原题：
这道题对于OD考试来讲，是输入一个 字符串 num 和 一个数字 n， 而力扣是 直接入参是 一个字符串 num 和一个数字 n 。仅此差别而已。
让你求的是， 从num 中删掉 n 个数字后， 得到的数值最小。 力扣给了更多提示，但OD机考的时候没有那么多提示，比如 n 大于 num.size() 怎么办， 没有写，应该是没有这类用例，所以你不用考虑。
言归正传， 从num 中移除n个数字，其他的顺序不变，怎么才能最小呢？
这个问题我没办法直接得到答案，但根据贪心算法的思想，我先搞定一小步，剩下的交给递归来搞，是不是就可以了呢？
一小步是什么呢？ 就是从 num 中，移除 1个 数字，使它变得最小，这个就简单了吧， 我只需要从高位到低位依次看过去，哪一位开始下降了，那么就移除它的前一位就好了。如果呈递增状态，则删除最后一个即可。
我们把每一位数值的大小看做一个小山峰的高度，于是就是谁的右边比它小，就干掉它就好了。
![]()
如上图所示，数字 35218642， 其中 2相对于5来讲下降了，那就把5干掉，让2取而代之。
![]()
如上图递增趋势，则干掉最后一位即可。
基于这个思路，我如果需要删掉N位，则我按照这个思路删掉一位之后得到一个新的num2，则此题目就可以转换成 从 num2 中删掉 n-1个数字。
直至0为止。
此外，如果我们删的很happy，最后搞的0开头，那么我们要把开头的0干掉，不然不是数字，比如 00123，我们要搞成123 。
如果全是0， 比如 123000 删除3位， 则得到000，那么就要改为 0 。
于是我的主函数这样写：
int main() {
string num;
int n;
cin >> num;
cin >> n;
//过载保护，如果n大于等于num的长度，则直接输出0即可。此处需根据题目要求自行变换实现方式
if (num.size() <= n)
{
cout << &#34;0&#34; << endl;
return 0;
}
//自己创造一个remove函数完成删除字符操作，具体怎么做，让它自己想办法
remove(num, n);
//自己写一个triml的函数，将左侧的0干掉，如果最后只剩下0，则把num改为0。
//c++有“引用”功能，所以函数里面改了外面也生效。
triml(num);
cout << num << endl;
}
那么 remove函数怎么实现呢？看下面
//注意 入参 num 是引用， 入参 n 是不是引用不重要，也不怎么占内存
void remove(string& num, int n) {
//走到这里可以保证num的size大于等于2，你知道为什么吗？
if (0 == n) {
return;
}
int idx = 1;
while (idx < num.size() ) {
//此处寻找从哪一位开始下降了，找到后就立马退出循环，如果没找到，则最终idx会等于num.size()
if (num[idx - 1] > num[idx]) {
break;
}
idx++;
}
/*
1. 递归调用自己，并把num 处理好，n处理好。
2. num要删除的是idx前面那个，因为idx是变小的那个，对于上面那个35218642来讲，idx是2的index。
3. 再注意：这里的 --idx 如果改为 idx-- 会怎么样？
4. 这里要给n减掉一个1。这里的 --n 如果改为 n-- 会怎么样？
*/
remove(num.erase(--idx, 1);, --n);
}
那么接下来，我们只需要实现一个triml函数即可。
因为我比较懒，不想写循环了，我干脆直接再来一个递归吧。这里我做了一个处理，当num 被 trim没了的时候，给他赋值个 “0”.
void triml(string& num){
if (num.size() == 0) {
num = &#34;0&#34;;
return;
}
if (num[0] == &#39;0&#39;) {
triml(num.erase(0, 1));
}
}
上面这段代码，改造成力扣模式后，提交是会超时的，有一个超大的用例，提供的是 111122223333 ，当然，1 和 2 和 3有非常多个。然后n = 50000 。
这份代码的优化，可以考虑将字符串改为用栈来做，递归也可以省了，大家有兴趣可以试试。
但我觉得我这份代码，在情急之下花半个小时写出来，应该能得大部分的分数。 |
|
转播
