leetcode-remove-k-digits

发表于   |   分类于 ，   |  

题目大意

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

　　给了你一个字符串代表非负整数，从其中去掉k位，使得剩下的字符串代表的整数最小并输出

题目分析

　　第一种我自己想的思路是：由于让整个数最小，那么应该从最高位开始保证每一位都尽可能的小，很自然地从左向右扫描字符串，得到结果的每一位，复杂度是O(n ^ 2)

　　第二种思路看了讨论区利用栈实现的O(n)算法（可以借助均摊分析，最多弹栈k次，压栈n次），思路是用一个辅助栈，然后扫描原串的每一位，在压入栈之前

先利用循环看栈顶的字符串是否比更大，如果大的话，就出栈，每次出栈，都代表remove了一位，因此出栈次数不能超过k，注意最后栈中的长度可能超过答案，只取前len(num) - k个即可

代码

　　第一种思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    
    private int len;
    private String str;
  
    private String helper(int idx, int remain) {
        StringBuilder ans = new StringBuilder();
        boolean begin = false;
        while (remain > 0) {
            int min = Integer.MAX_VALUE;
            int loc = -1;
            for (int i = idx; i <= len - remain; i++) {
                if (str.charAt(i) < min) {
                    loc = i;
                    min = str.charAt(i);
                }
            }
            if (str.charAt(loc) != '0') {
                begin = true;
            }
            if (begin) { 
                ans.append(str.charAt(loc));
            }
            remain--;
            idx = loc + 1;
        }
        return ans.toString();
    }
    
    public String removeKdigits(String num, int k) {
        len = num.length();
        str = num;
        
        if (k == len) {
            return "0";
        }
        if (k == 0) {
            return num;
        }
        String ret = helper(0, len - k);
        if (ret.equals("")) {
            return "0";
        }
        return ret;
    }
}

　　时间复杂度 O(n^2)

　　第二种思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public String removeKdigits(String num, int k) {
        int len = num.length();
        if (k == len) {
            return "0";
        }
        if (k == 0) {
            return num;
        }
        int remain = len - k;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char ch = num.charAt(i);
            while (!stack.empty() && stack.peek() > ch && k > 0) {
                stack.pop();
                k--;
            }
            stack.push(ch);
        }
        StringBuilder ans = new StringBuilder();
        int size = stack.size();
        boolean begin = false;
        for (int i = 0; i < remain; i++) {
            if (stack.get(i) != '0') {
                begin = true;
            }
            if (begin) {
                ans.append(stack.get(i));
            }
        }
        String ret = ans.toString();
        return ret.equals("") ? "0" : ret;
    }
}

　　时间复杂度 O(n)