Leetcode日记–402. Remove K Digits

发布于 2020-11-15  119 次阅读


题目如下:

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

思路:

很显然,对于位数一样的数字来说,高位决定了其大小,因此在本题中,我们的目标就是使得高位数字尽可能小。

算法策略:

1.对于给定序列[D0D1....Dn],我们需要找到第一个i,使得Di>D(i+1).这时我们删去Di。

注意:若本轮遍历中没有找到满足条件的数则把最后一个删去即可。

2.对于剩下的序列,我们继续执行step1中的算法,直到删除的位数达到k个。

方法一:

代码如下:

class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length()==k) {
            return "0";
        }
        StringBuilder s = new StringBuilder(num);
        for (int j = 0; j < k; j++) {
            for (int i = 0; i <s.length() - 1; i++) {
                if (s.charAt(i)>s.charAt(i+1)){
                    s.delete(i,i+1);
                    break;
                }
                //如果遍历到最后也没有删掉则把最后一位删掉
                if (i==s.length()-2){
                    s.delete(i+1,i+2);
                }
            }
        }
        while(s.length()>1&&s.charAt(0)=='0'){
            s.delete(0,1);
        }
        return s.toString();
    }
}

但是这种方法的最坏时间复杂度是O(kn),即整个数组需要遍历k遍。因此我们使用一个单调栈来减小时间复杂度。

方法二:

本方法使用了单调栈,这种结构顾名思义,就是满足单调性的栈结构。

当我们使用单调栈的时候,若遇到了比当前栈顶小的元素则将栈顶元素pop出来,并一直pop,直到:

1.当前栈顶元素小于遍历到的元素,则遍历到的元素可以入栈。

2.已经pop了k个元素了,则后面的所有其他元素直接入栈。

3.栈为空

以“1432219”为例的过程

最终,得到的栈低至栈顶元素则为答案。(也就是说pop出来以后还需要逆序一下才行)。

考虑到栈的特点是后进先出,如果通过栈实现,则需要将栈内元素依次弹出然后进行翻转才能得到最小数。为了避免翻转操作,可以使用双向队列代替栈的实现。

代码如下:

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> deque = new LinkedList<Character>();
        int length = num.length();
        for (int i = 0; i < length; ++i) {
            char digit = num.charAt(i);
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
                deque.pollLast();
                k--;
            }
            deque.offerLast(digit);
        }
        
        for (int i = 0; i < k; ++i) {
            deque.pollLast();
        }
        
        StringBuilder ret = new StringBuilder();
        boolean leadingZero = true;
        while (!deque.isEmpty()) {
            char digit = deque.pollFirst();
            if (leadingZero && digit == '0') {
                continue;
            }
            leadingZero = false;
            ret.append(digit);
        }
        return ret.length() == 0 ? "0" : ret.toString();
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/remove-k-digits/solution/yi-diao-kwei-shu-zi-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法三:

这个是在评论区看到的,觉得也蛮巧妙的。

来自用户夜殇

分享一个思路,依据数字位数越高影响越大,从最高位挑选数字。例:num = 1432219, k=3,删去k=3个数字,那么就是保留length-k=7-3=4个数字。首先需要挑选首位数字,保证尽量小并且在num中的位置尽量靠左。可以将num = 1432219分为 1432 和 219两部分(保留最后3个作为保底,在之前的4位中找最小)此时start = 0, end = k。在[start,end]中选取一个最小的进行保留,返回最小数字的下标min_pos。找第二位的时候start = min_pos + 1. end +=1 如此类推直到选完 n-k 次。

对于前缀0,选择不把选取过程中的首个0加入结果字符串ans 但是 算作一次挑选step进行处理。

代码如下:

class Solution {
public:
    string removeKdigits(string num, int k) {
        int length = num.size();
        int step = num.size() - k;
        string ans = "";
        int min_pos = -1; 
        while (step > 0) {
            int start = min_pos + 1;
            char min_val = num[start];
            for (int i = length - step; i >= start; i--) {
                if (num[i] <= min_val) {
                    min_val = num[i];
                    min_pos = i;
                }
            }
            if (min_val == '0' && ans.size() == 0){
                step--;
            }
            else {
                ans.push_back(min_val);
                step--;
            }
        }
        
        return ans == "" ? "0" : ans;
    }
};

关于单调栈的总结:

在本题中,我们想要数字的高位尽可能地为递增序列,同时,又不想进行多遍的遍历,因此我们需要一个单调栈“记住”之前的结果。

那么我们什么时候应该使用单调栈呢?

当我们在寻找某个波谷,那么我们使用单调递增栈,留下波谷;

当我们在寻找某个波峰,那么我们使用单调递减栈,留下波峰。

使用单调栈的情况

在本题中,我们要尽可能地将波谷计入答案中,因此使用了单调递增栈。


你好哇!欢迎来到雷公马碎碎念的地方:)