2.3 Remove k Digits 405
Description
Given a non-negative integernumrepresented as a string, removekdigits 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.
Hint
greedy stack
Method
greedy :
- if we want to delete k digits to get a smallest number, we need to compare each digit. We should delete a digit if it has a higher value and hold a high position.
1321 --> 3 > 2 and 3 is showing before so we need to delete 3
so we can use a tmp char array to hold the number
when we move the i from 0 - n at original number, we compare tmp value with the value if we use current digits if smaller we update the tmp.
so we need to take care of the remain digits we can use to compare.
- using stack to store tmp
Time & Space
o(n)
Code
public String removeKdigits(String num, int k) {
if (num == null || num.length() <= k || num == "0"){
return "0";
}
// (1) (n - i
>
remain - index): have enough remaining digits to be compared
// (2) (res[index - 1]
>
nums[i]): at this time, the (index-1) is the newest added digit,
// compare this digit with the current num, if the res is greater and you have enough
// remaining digits to be compared, decrease the index(it ensures that the future added digit is
// always smaller than before and the size is remain) until get the right and 'safe' position
int remain = num.length() - k;
char[] nums = nu m.toCharArray();
char[] res = new char[remain];
int index = 0;
for (int i = 0; i < nums.length; i++){
while ((nums.length - i > remain - index) && (index > 0 && nums[i] < res[index - 1])){
index--;
}
if (index < remain){
res[index++] = nums[i];
}
}
index = -1;
while (++index < remain){
if (res[index] != '0'){
break;
}
}
String s = new String(res).substring(index);
return s;
}
code : stack
Deque<Character> stack = new LinkedList<Character>();
int i = 0;
while (i < num.length()){
while (k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(i)){
stack.pop();
k--;
}
stack.push(num.charAt(i));
i++;
}
while (k > 0){
stack.pop();
k--;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()){
sb.append(stack.pop());
}
sb.reverse();
while (sb.length() > 1 && sb.charAt(0) == '0'){
sb.deleteCharAt(0);
}
return sb.toString();