402. Remove K Digits
Given a non-negative integer num represented as a string, remove k digits 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.
Rust Solution
struct Solution;
impl Solution {
fn remove_kdigits(num: String, mut k: i32) -> String {
let mut stack: Vec<char> = vec![];
for c in num.chars() {
while let Some(&top) = stack.last() {
if k > 0 && top > c {
stack.pop();
k -= 1;
} else {
break;
}
}
stack.push(c);
}
while k != 0 {
stack.pop();
k -= 1;
}
let res: String = stack.into_iter().skip_while(|&c| c == '0').collect();
if res.is_empty() {
"0".to_string()
} else {
res
}
}
}
#[test]
fn test() {
let num = "1432219".to_string();
let k = 3;
let res = "1219".to_string();
assert_eq!(Solution::remove_kdigits(num, k), res);
let num = "10200".to_string();
let k = 1;
let res = "200".to_string();
assert_eq!(Solution::remove_kdigits(num, k), res);
let num = "10".to_string();
let k = 2;
let res = "0".to_string();
assert_eq!(Solution::remove_kdigits(num, k), res);
}
Having problems with this solution? Click here to submit an issue on github.