Remove k digits

Remove k digits from a number to leave the smallest possible result, using a monotonic increasing stack of digits.

The idea

A number is smaller when its leftmost differing digit is smaller. So whenever the next digit is smaller than the one on top of the stack, popping that bigger digit (if there is still a removal to spend) always helps, or at worst does not hurt. Any removals left over once every digit has been read are spent trimming the largest, right-most digits that remain.

Code

public static string RemoveKdigits(string num, int k) {
    var stack = new Stack<char>();
    foreach (char d in num) {
        while (k > 0 && stack.Count > 0 && stack.Peek() > d) {
            stack.Pop(); k--;
        }
        stack.Push(d);
    }
    while (k-- > 0) stack.Pop();
    var digits = stack.Reverse().SkipWhile(c => c == '0').ToArray();
    return digits.Length == 0 ? "0" : new string(digits);
}

Tips

• Each pop uses up one of the k removals, so stop popping as soon as k reaches 0, even if a bigger digit is still on top.
• Leading zeros can appear after popping (e.g. "10200" with k=1 gives "0200"); strip them, and if nothing is left the answer is "0".

In the .NET library

stack.Reverse() walks a Stack<char> from top to bottom, which here is also left to right, since digits were pushed in reading order with only the top ever popped.