【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>

閱讀更多 碼農之屋 的文章

關鍵字: 移掉 示例 貪心