402. Remove K Digits
Medium
Given string num representing a non-negative integer num
, and an integer k
, return the smallest possible integer after removing k
digits from num
.
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.
Constraints:
1 <= k <= num.length <= 105
-
num
consists of only digits. -
num
does not have any leading zeros except for the zero itself.
Solution:
class Solution {
/**
* @param String $num
* @param Integer $k
* @return String
*/
function removeKdigits($num, $k) {
if (strlen($num) == $k) {
return '0';
}
$ans = [];
$stack = [];
for ($i = 0; $i < strlen($num); $i++) {
$digit = $num[$i];
while ($k > 0 && !empty($stack) && $stack[count($stack) - 1] > $digit) {
array_pop($stack);
$k -= 1;
}
array_push($stack, $digit);
}
for ($j = 0; $j < $k; $j++) {
array_pop($stack);
}
foreach ($stack as $c) {
if ($c == '0' && empty($ans)) {
continue;
}
array_push($ans, $c);
}
return implode($ans) ? implode($ans) : '0';
}
}
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!