【LeetCode 贪心算法系列】402 移掉K位数字

一、题目描述

给定一个以字符串表示的非负整数 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。

二、解决思路

使用贪心算法 + 栈，若要去掉某一个数字，为了使得到的新数字最小，需要尽可能的让新数字优先最高位最小，其次次高位最小，以此类推。

三、Java代码实现

<code>public String removeKdigits(String num, int k) {
    if (num.length()== k) {
        return "0";
    }

    Stack<integer> result = new Stack<>();
    for (int i = 0; i < num.length(); i++){
        int tmp= num.charAt(i) - '0';

        while (result.size() != 0 &&result.peek() > tmp && k != 0) {
            result.pop();
            k--;
        }

        if (result.size()== 0 && tmp == 0) {
            continue;
        }

        result.push(tmp);
    }

    if (result.size()== 0) {
        return "0";
    }

    while (k!= 0) {
        result.pop(); 

        k--;
    }

    StringBuffer results = new StringBuffer();
    while (result.size() != 0) {
        results.append(result.pop());
    }

    return results.reverse().toString();
}/<integer>/<code>

閱讀更多 碼農之屋 的文章

關鍵字: 移掉 示例 贪心