visual walkthrough
Remove K Digits
A greedy monotonic stack that builds the smallest number.
The idea
The leftmost digits matter most. So whenever a digit is followed by a smaller one, deleting the bigger digit makes the number smaller right away. A stack that only allows increasing digits does exactly that, popping bigger digits while it still has deletions left.
If digits run out of descents, remove from the end, where the biggest digits are.
Complexity
| approach | time | space |
|---|---|---|
| Try every removal | O(C(n, k) · n) | O(n) |
| Monotonic stack | O(n) | O(n) |