402. Remove K Digits

QUESTION:

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.
``````

EXPLANATION:

1. 我们先创建一个栈
2. 把第一个num.array的第一个数放在第一个
3. 第二个数到的时候，先判断长度是否还够往前挤，如果够的话，那么判断是否比前面的数小
4. 如果比前面的数小，就把该数往前挤，这样就能得到位置
5. 重复2-4步，直到整个数组被压缩到对应位置

SOLUTION:

``````    public static String removeKdigits(String num, int k) {
char[] chars = num.toCharArray();
int remain = num.length() - k;
char[] result = new char[remain];
int index = 0;
for(int i = 0;i<chars.length;i++){
while ((chars.length - i > remain - index) && (index > 0 && chars[i]<result[index-1])) index--;
if(index < remain) result[index++] = chars[i];
}

index = -1;
while (++index<remain){
if(result[index] != '0') break;
}
String s = new String(result).substring(index);
return s.length() == 0 ? "0" : s;
}
``````
>