题目：Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
- The length of num is less than 10002 and will be ≥ k.
- The given num does not contain any leading zero.
Example 1:Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
分析：
题目是LeetCode上的一个题目：
大意就是：有一个数字（个数>K），删掉其中的 K 个数字，使组成的新的数字最小。
小注：数字的长度很长，用String型存贮，输出的数字不以0开始。
一开始以为是从按照数字的大到小进行删除，但是举例子发现并不是这么简单。
例子：2159 删掉一个数，删掉9是215，删掉2是159。 明显删掉2比9的结果更小。分析得结论是数字的位置比数字的大小更重要。
应该是从高位向低位检索，用比自己小的数来替换自己的位置。 可以理解为若是右边的比左边的小，则删除左边的。
这是每一步求的局部最优解，最终得到全局最优解，也是贪心算法的思想。
这是第一次在LeetCode上做题，emmmm，每一次提交的错误信息都会告诉你，这个很贴心。
先放一个我的错误代码
class Solution {
//思路有问题public String removeKdigits(String num, int k) {
String newString = "";char temp[] = new char[num.length()];for (int i = 0; i < num.length(); i++)temp[i] = num.charAt(i);int count = k;//删减次数//若长度和k相同，直接返回0if (num.length() == k)return "0";else {
//只遍历一次，也是错误的地方for (int i = 0; i < num.length(); i++) {
if (count > 0) {
if (i < num.length() - 1) {
if (temp[i] <= temp[i + 1]) {
//若是左边比不比右边，则加到新的串里去newString += temp[i];} else//否则就删掉这个数count--;}else {
//当i到了最后一个数，无法比较，直接加进去newString += temp[i];}} else {
若是count等于零了，剩下的全部加进去newString += temp[i];}}} int zero=0;//判断一开始等于零的个数for(int x=0;x<newString.length();x++) {
if(newString.charAt(x)!='0')break;else zero++; }//若是比较之后count不等于0，则从后向前删掉newString=newString.substring(zero, newString.length()-count);if(newString.length()==0)return "0"; return newString;}
}
改进
这时候出的问题是，我发现，添加一个新的字符串是不对的，因为一次循环是解决不了问题的。像上面的例子，我一次遍历后，删掉9，然后都加入了字符串，从后向前删除。最后只剩下了1。
应该采用删除的思路，将不合格的字符从字符串中删掉。
class Solution {
public String removeKdigits(String num, int k) {
char temp[] = new char[num.length()];int count = k;int time=0;if (num.length() == k)return "0";else {
int max=num.length();Loop:for(int j=0;j<max;j++) {
for (int i = 0; i < num.length(); i++) {
if (count > 0) {
if (i < num.length() - 1) {
//不合格的删掉if (num.charAt(i) > num.charAt(i+1)) {
num=num.substring(0, i)+num.substring(i+1,num.length());count--;//下一次从前一个开始于后一个比较time=i-1;break;} }}else break Loop;}} }int zero = 0;for (int x = 0; x < num.length(); x++) {
if (num.charAt(x) != '0')break;elsezero++;}num = num.substring(zero, num.length() - count);if (num.length() == 0)return "0";return num;}
}
只能说尬的一批，提交中是垫底了，需要优化。
这个代码中，每一次变化都是在用subString方法，效率巨慢，而且循环也浪费了时间。
借鉴大佬的算法
采用栈，每次都和栈顶元素进行比较，比栈顶元素小，则栈顶元素出栈，继续与栈顶比较，若大于栈顶，则入栈
class Solution {
public String removeKdigits(String num, int k) {
// 新整数的最终长度 = 原整数长度 - kint newLength = num.length() - k;// 创建一个栈，用于接收所有的数字char[] stack = new char[num.length()];int top = 0;for (int i = 0; i < num.length(); ++i){
// 遍历当前数字char c = num.charAt(i);// 当栈顶数字大于遍历到的当前数字，栈顶数字出栈（相当于删除数字），直到栈顶小于待加入的数字while (top > 0 && stack[top - 1] > c && k > 0) {
top -= 1;k -= 1;}// 待加入的数字入栈stack[top++] = c;}// 找到栈中第一个非零数字的位置int offset = 0;while (offset < newLength && stack[offset] == '0')offset++;//返回新建的字符串对象，用栈中的元素组成，减去零的长度return offset == newLength ? "0" : new String(stack, offset, newLength - offset);}
}
总结：
大神就是大神，就是牛逼，不过这样的逻辑依旧只能84%，很是好奇其他的代码是啥样的。
继续努力。