移掉K位数字

[louzhedong]

习题

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

思路

除了第一个数字，对于每个数字，我们都能确定它和它前一个数字的大小，进行比较，留下较小的一个。

解答

javascript

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
    var stack = [];
    for (let i = 0, len = num.length; i < len; i++) {
        while(k > 0 && stack.length > 0 && stack[stack.length - 1] > num[i]) {
            stack.pop();
            k--;
        }
        if (num[i] != '0' || stack.length > 0) {
            stack.push(num[i]);
        }
    }
    while(k > 0) {
        stack.pop();
        k--;
    }
    return stack.length == 0 ? '0' : stack.join('');
};

go

func removeKdigits(num string, k int) string {
    stack := make([]rune, 0)

    for _, c := range num {
        for k > 0 && len(stack) > 0 && stack[len(stack) - 1] > c {
            stack = stack[0: len(stack) - 1]
            k--
        }
        if (c != '0' || len(stack) > 0) {
            stack = append(stack, c)
        }
    }
    for k > 0 && len(stack) > 0 {
        stack = stack[0: len(stack) - 1]
        k--
    }

    if len(stack) == 0 {
        return "0"
    } else {
        return string(stack)
    }
}