# Java solution with a simulated stack in O(N)

• The original idea is to simulate a stack in which all characters are kept to return, all others are to be delete.

The time complexity is O(N), the space complexity is O(1) if we ignore the char array.

``````public String removeKdigits(String num, int k) {
if (num.length() == k) {
return "0";
}
char[] array = num.toCharArray();
// the point is to delete the first k num[i]
// that num[i] > num[i + 1]
// we simulate a stack, end is the top of stack
// all characters in the stack are what we want to return
int end = -1;
int count = 0;
for (int i = 0; i < array.length; i++) {
// when do we need to keep array[i] in stack for now
if (end == -1 || array[i] >= array[end] || count == k) {
array[++end] = array[i];
} else {
// when do we need to delete array[end]
while (count < k && end >= 0 && array[end] > array[i]) {
end--;
count++;
}
array[++end] = array[i];
}
}
// if count < k, all elements in stack is in ascending order
// we need to pop out the top (k - count) elements
while (count < k) {
end--;
count++;
}