BiruLyu
7/26/2017 - 1:07 AM

## 402. Remove K Digits(#Stack).java

``````public class Solution {
public String removeKdigits(String num, int k) {

int top = 0;
int len = num.length();
int left = len - k;
char[] ans = new char[left];
for (int i = 0; i < len; i++) {
char cur = num.charAt(i);
while (len - i + top > left && top > 0 && cur < ans[top - 1]) {
top--;
}
if (top < left) {
ans[top++] = cur;
}
}
int j = 0;
while (j < left && ans[j] == '0') j++;
return j == left ? "0" : new String(ans, j, left - j);
}

}``````
``````public String removeKdigits(String num, int k) {
if (num == null || num.length() == 0 || k == 0) {
return num;
}
if (k == num.length()) return "0";
int digits = num.length() - k;
// stack need to be the same length with num.
char[] stack = new char[num.length()];
int top = 0;
for (int i = 0; i < num.length(); i++) {
// if the previous character in stack is larger than the current one, then removing it will get a smaller number
// but we can only do so when k > 0
while (top > 0 && k > 0 && num.charAt(i) < stack[top - 1]) {
top--;
k--;
}
stack[top++] = num.charAt(i);
}
int j = 0;
while (j < digits && stack[j] == '0') j++;
return j == digits ? "0" : new String(stack, j, digits - j);
}``````
``````public class Solution {
public String removeKdigits(String num, int k) {
if (num == null || num.length() < 1) return "";
StringBuilder res = new StringBuilder();
for (char c : num.toCharArray()) {
int len = res.length();
while (len > 0 && c < res.charAt(len - 1) && k > 0) {
res.setLength(len - 1);
len--;
k--;
}
res.append(c);
}
while (k > 0) {
int len = res.length();
res.setLength(len > 1 ? len - 1 : 0); // avoid out of index
k--;
}
//int idx = 0;
while (res.length() > 0 && res.charAt(0) == '0') {
res.deleteCharAt(0);
//idx++;
}
return res.length() == 0 ? "0" : res.toString();
}
}``````