5月1日，劳动节第一天，花了大半个下午思考这道题，独立思考解决的感觉很爽。
题干
https://leetcode.com/problems/remove-k-digits/
对一个数字num删掉k个字符，求怎么删使留下字符组成的数字是最小的？
思考过程
好吧，一个很费脑的感觉，又是一个掉脑细胞的问题。 解决这种问题，其实考的就是观察能力和直觉。怎么删使留下的数字最小？本帅脑子里并没有相关的知识模型，学了十几年的数学里也没有这玩意啊，那就自己总结吧。
第一步就是在纸上多演示几个例子，感受这种过程，只有熟悉过程才能总结。
经历了多种猜想，先从简单的开始，删一个怎么删？写几遍就会发现，被删掉的数字 是这样被找到的： 从最左边开始找，第一个峰值，所谓峰值，就是 大于等于左边的数，大于右边的数，为什么是这个呢？ 如果你删峰值左边的数，其实数字是变大了，不如删峰值呢，如果你删右边的，还是不如删峰值。
好啦，那删两个怎么删？ 设数列 （x1,x2,x3….xl），删掉 第 m 和 n 个数是最小的，设删掉后的数字是 f（m,n）, 我们能不能转化成删掉一个使最小，再删掉一个使最小呢 ? 验证一下，的确是的，于是我们得出一个结论：
如果 f(m,n) 是随意删掉两个的后最小的，则我们一个一个删，第一次删1 个 ，f(x)是删掉第x个的最小值，第二次删 是在第一次删掉的基础上，删掉 第y个后最小，为 f(x,y) ,则 f(x,y) = f(m,n)
证明：
f(x,n)<=f(m,n) 因为x是删掉第n个后删一个最小的，
f(m,n) <=f (x,y) 因为这是 f(m,n)的定义
f (x,y)<=f(x,n) ， 这是 题目要求，
于是
f(x,n)<=f(m,n) <=f (x,y)<=f(x,n)
也就是说，我们可以把删两次最小 转化成 一次删一个，使其最小。那对于多个，其实也是一样的，只要把y改成多维的就好啦。
代码
我们求删掉k个最小，只需求删 k次一个的，只要让按删一个最小的算法 进行k次就好啦
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
class Solution {
public static String removeKdigits(String num, int k) {
//对特殊情况处理
if (k == 0 || num.length() == 0) {
return num;
}
if (k == num.length()) {
return "0";
}
//转换成int数组
List<Integer> list = new ArrayList<>();
char[] chars = num.toCharArray();
for (char c : chars) {
list.add(c - '0');
}
for (int i = 0; i < k; i++) {
//找到一个峰值然后删掉
int shoudRemoveIndex = 0;//应该删掉的数的下标
do {
if (shoudRemoveIndex == list.size() - 1) {
break;
}
if (list.get(shoudRemoveIndex) > list.get(shoudRemoveIndex + 1)) {
//找到了一个峰值
break;
}
shoudRemoveIndex++;
} while (shoudRemoveIndex <= list.size() - 1);
list.remove(shoudRemoveIndex);
}
//删掉开头的0
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
if (iterator.next() == 0) {
iterator.remove();
} else {
break;
}
}
StringBuilder res = new StringBuilder();
iterator = list.iterator();
while (iterator.hasNext()) {
res.append(iterator.next());
}
String resString = res.toString();
return resString.isEmpty() ? "0" : resString;
}
}
总结
每次解决一次看起来自己做不出来的题的时候都很开心，成就感很爽
