331. Remove K Digits
You are given a string num representing a non-negative integer, and an integer k. Delete exactly k digits from num so that the digits that remain — kept in their original left-to-right order — spell the smallest possible number. Return that number as a string.
Canonical form: the returned string must carry no leading zeros ("0200" becomes "200"), and if the deletions leave nothing at all (or only zeros), return exactly "0".
The input num itself has no leading zeros unless it is the single digit "0".
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Deleting the digits 4, 3 and the second 2 leaves "1219", the smallest number reachable with exactly three deletions.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Removing the leading 1 leaves "0200"; stripping the now-leading zero gives "200". No other single deletion beats it.
Constraints:
- 1 ≤ k ≤ num.length ≤ 10⁵
- num consists of digits only.
- num has no leading zeros, except when num itself is "0".
Hints:
Think about which single deletion helps the most: removing the first digit that is bigger than its right neighbor. Why? Because that position is where a smaller digit can be promoted to a more significant place.
Doing that k times is O(n·k). A monotonic stack does all k deletions in one pass: scan left to right, and while the top of the stack is bigger than the incoming digit (and you still have deletions left), pop it. Watch two endgames — leftover deletions when the digits never descend, and leading zeros in the result.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: num = "1432219", k = 3
Expected output: "1219"