算法-贪心-移掉K个数后的最小数（remove-k-digits）

阳光穿透心脏的1/2处 2023-07-25 12:52 86阅读 0赞

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/remove-k-digits/

## 1.2 题目描述 ##

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

# 2 暴力贪心法 #

## 2.1 思路 ##

经过观察，每次移除一位时，要让移除后的数最小，则从左遍历，如果递增则继续，如果发生减小则停止遍历，并将最高点的那个数删除即可。

删除k个数时，需要遍历k次。

这个代码很容易写错，有一些边界条件如删除后开头都是0、元素全部被移除只剩0等需要注意。

## 2.2 代码 ##

class Solution { 
        public String removeKdigits(String num, int k) { 
            if(k >= num.length())
            return "0";
    
            // 每次移除左数第一个0之前的最大数，可以使得移除后的数最小
            char[] nums = num.toCharArray();
            // 将数组元素全部放到ArrayList方便移除
            List<Character> numsList = new ArrayList<>(k);
            for(int i = 0; i < nums.length; i++){ 
                numsList.add(nums[i]);
            }
    
            // 存放当前次遍历到的最大数值
            int max = 0;
            // 存放当前目标移除元素位置
            int remove = 0;
           
            while(k > 0){ 
                int i = 0;
                int prevLength = numsList.size();
                for(i = 0; i < numsList.size(); i++){ 
                    // 当前元素的int数值
                    int current = numsList.get(i) - '0';
                    if(current > max){ 
                        // 大于max时就作为移除备选
                        remove = i;
                        max = current;
                    }else if(current < max){ 
                        // 当遇到比前一个数字小时，就结束该趟遍历，取最后一个最大的数移除
                        // 移除目标位置的数字
                        numsList.remove(remove);
                        // 重置max和remove
                        max = 0;
                        remove = 0;
                        // 结束这一趟遍历
                        break;
                    }
                }
                if(i == prevLength){ 
                    // 此时没有0，已经扫描到最后数字
                    // 或只有0
                    // 移除目标位置的数字
                    numsList.remove(remove);
                    // 重置max和remove
                    max = 0;
                    remove = -1;
                }
                k--;
            }
    
            String resultStr = "";
            // 将删除后的字符List拼接为字符串
            for(int i = 0; i < numsList.size(); i++){ 
                if(resultStr.length() != 0 || numsList.get(i) != '0'){ 
                    resultStr += numsList.get(i);
                }
            }
            // 可能剩余全为0了，此时返回"0"
            return resultStr.length() == 0 ? "0" : resultStr;
        }
    }

## 2.3 时间复杂度 ##

O(n^2)

## 2.4 空间复杂度 ##

O(n)

# 3 基于双端队列优化的贪心法 #

## 3.1 思路 ##

经过观察，之前的暴力贪心法大方向没错，只不过每趟遍历时重复计算了前面部分。

那么要避免重复计算，就能想到使用栈来存放已经计算好的结果。

具体来说，将数字从左往右遍历：

1.  只要递增就入队
2.  如果发现比队尾元素小就先将队尾元素出队，表示移除了当前最高位的局部最大数以使得移除后的数最小
3.  如果仍需移除元素，就继续将当前元素和新的队尾元素对比，并继续1-3的流程
4.  持续1-3的步骤，直到已经移除了k个数或已经遍历完原始数组
5.  此时有两种可能：
    
     *  存在递增序列，导致没有移除够k个数，则继续移除若干数直到共移除k个数
     *  提前移除完k个数，则将剩余数全部依次入队尾
     *  没有第三种可能
6.  此时我们已经得到移除了k个数后的charList，只需要依次遍历，并将数放入StringBuidler拼接即可。  
    此时必须注意，有可能前几位都是’0’，所以拼接时必须排除这些首个非’0’字符前的’0’。所以最后返回结果时，可能StringBuilder没有任何字符，此时需要判断后返回"0"。

## 3.2 代码 ##

class Solution { 
        public String removeKdigits(String num, int k) { 
            if(k >= num.length())
                return "0";
    
            // 每次移除左数第一个0之前的最大数，可以使得移除后的数最小
            char[] nums = num.toCharArray();
            // 存放移除后的所有char
            LinkedList<Character> charList = new LinkedList<>();
    
            int i = 0;
            while(i < nums.length && k > 0){ 
                if(charList.size() == 0){ 
                    charList.add(nums[i]);
                    i++;
                    continue;
                }
                if(nums[i] >= charList.peekLast()){ 
                    // 只要当前元素大于等于列表尾元素就入列
                    charList.add(nums[i]);
                    i++;
                }else{ 
                    // 当前元素小于列首元素就出列
                    charList.pollLast();
                    // 表明出列了一个元素
                    k--;
                    // 下一趟还需要从当前位置开始判断，所以i不变
                }
            }
    
            // 持续递增时的处理，将k个列首最大元素移除
            while(k > 0){ 
                charList.pollLast();
                k--;
            }
            // 如果已经将k个数移除，那么剩下的数全部入列
            while(i < nums.length){ 
                charList.add(nums[i]);
                i++;
            }
    
            // 将列表中元素按顺序加入StringBuilder，
            // 注意如果无大于0的元素时，遇到0就忽略，从第一个非0元素开始加入
            StringBuilder result = new StringBuilder();
            Iterator<Character> iterator = charList.iterator();
            while(iterator.hasNext()){ 
                char c = iterator.next();
                if(result.length() == 0 && c == '0'){ 
                        continue;
                }
                result.append(c);
            }
            
            // 有可能全0，此时就返回"0"
            return result.length() == 0? "0" : result.toString();
        }
    }

## 3.3 时间复杂度 ##

O(n)

## 3.4 空间复杂度 ##

O(n)