You are given a string num holding a non-negative integer and an integer k. Remove exactly k digits so that the remaining number is as small as possible, and return it as a string. Remove any leading zeros from the result, and return "0" if nothing is left.
"0200", which becomes "200".- 1 <= k <= num.length <= 10^5
- `num` has only digits
- `num` has no leading zeros except for the number zero itself
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every way to choose k digits to delete, which is exponential, or removes one digit at a time by trying all positions, which is O(n * k). Greedy thinking helps: a number gets smaller fastest by lowering its leftmost digits. Whenever a digit is followed by a smaller digit, deleting the bigger one improves the number at the earliest possible position. A monotonic increasing stack applies that rule in one pass. If deletions are left over, the stack is non-decreasing, so the best digits to drop are the last ones.
Algorithm
- Create an empty stack of digits.
- For each digit
d: whilek > 0, the stack is not empty and its top is greater thand, pop and decreasek. Then pushd. - If
k > 0remains, popkmore digits from the end. - Join the stack, strip leading zeros, and return
"0"if the result is empty.
O(n)Space: O(n)"112" with k = 1 or "12345" never trigger a pop during the scan, so forgetting the leftover k step returns a number that is too long. Also handle "10" with k = 2, which must give "0", not an empty string.class Solution: def removeKdigits(self, num: str, k: int) -> str: stack = [] for d in num: while k > 0 and stack and stack[-1] > d: stack.pop() # a bigger digit before a smaller one k -= 1 stack.append(d) if k > 0: stack = stack[:-k] # drop leftover digits from the end res = ''.join(stack).lstrip('0') return res if res else '0'