Leetcode-402-移除K个数

Leecode-409-移掉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。

方法 ： 贪心算法

官方很好的题解 ： https://leetcode-cn.com/problems/remove-k-digits/solution/yi-diao-kwei-shu-zi-by-leetcode-solution/

class Solution {
    public String removeKdigits(String num, int k) {
        LinkedList<Character> stack = new LinkedList<>();

        // 每次丢弃一次，k 减去 1。当 k 减到 0 ，我们可以提前终止遍历。
        for(char digit : num.toCharArray()){
            while(stack.size() > 0 && k > 0 && stack.peekLast() > digit){
                stack.removeLast();
                k -= 1;
            }
            stack.addLast(digit);
        }

        // 而当遍历完成，如果 k 仍然大于 0。
        // 不妨假设最终还剩下 x 个需要丢弃，那么我们需要选择删除末尾 x 个元素。
        for(int i = 0;i < k;i++){
            stack.removeLast();
        }

        StringBuilder ret = new StringBuilder();
        // 处理删除后的前导0，直接跳过即可
        boolean leadingZero = true;
        for(char digit:stack){
            if(leadingZero && digit == '0') continue;
            leadingZero = false;
            ret.append(digit);
        }

        // 最终数字序列为空的话,返回0
        if(ret.length() == 0){
            return "0";
        }
        return ret.toString();
    }
}

复杂度分析

• 时间复杂度 ： O(n)，其中 n 为字符串的长度。尽管存在嵌套循环，但内部循环最多运行 k次。由于0<k≤n，主循环的时间复杂度被限制在 2n以内。对于主循环之外的逻辑，它们的时间复杂度是 O(n)，因此总时间复杂度为 O(n)。
• 空间复杂度 ： O(n) 栈所需要的空间大小

打赏