Question
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
https://leetcode.com/problems/remove-k-digits/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public String removeKdigits(String num, int k) {
Stack<Character> stack = new Stack<>();
for (char c : num.toCharArray()){
while (!stack.isEmpty() && k > 0 && c < stack.peek()){
stack.pop();
k--;
}
stack.push(c);
}
while (k-- > 0) stack.pop();
StringBuilder sb = new StringBuilder();
boolean zero = true;
for (int element : stack){
if (element == '0' && zero) continue;
else zero = false;
sb.append(element - '0');
}
return sb.length() == 0 ? "0" : sb.toString();
}
}
|
Time complexity: O(n)
Space complexity: O(n)