-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathremoveKDigits.java
More file actions
49 lines (48 loc) · 1.88 KB
/
removeKDigits.java
File metadata and controls
49 lines (48 loc) · 1.88 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
public class removeKDigits {
public static void main(String[] args){
}
/* The first algorithm is straight-forward.
Let's think about the simplest case: how to remove 1 digit from the number so that the new number is the smallest possible？
Well, one can simply scan from left to right, and remove the first "peak" digit;
the peak digit is larger than its right neighbor. One can repeat this procedure k times,
The above algorithm is a bit inefficient because it frequently remove a particular element from a string and has complexity O(k*n).
One can simulate the above procedure by using a stack, and obtain a O(n) algorithm.
Note, when the result stack (i.e. res) pop a digit, it is equivalent as remove that "peak" digit.
* */
public String removeKDigits(String num, int k){
// corner case: k > num.length
if(k >= num.length()){
return "0";
}
Stack<Character> stack = new Stack<>();
int i = 0;
while(i < num.length()){
Character cur = num.charAt(i);
// whenever meet a digit which is less than the previous digit, discard the previous one
// at current string, the previous one is a "peak"
while(!stack.isEmpty() && k > 0 && cur > stack.peek()){
stack.pop();
k --;
}
stack.push(cur);
i ++;
}
// corner case like: 019
while(k > 0){
stack.pop();
k--;
}
// construct the string from stack
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
sb.reverse();
// remove all leading zeros
while(sb.length()>1 && sb.charAt(0) == '0'){
sb.deleteCharAt(0);
}
return sb.toString();
}
}