LeetCode402-移掉K位数字

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/remove-k-digits/

中文链接：https://leetcode-cn.com/problems/remove-k-digits/

题目详述

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

  • num 的长度小于 10002 且 ≥ k。
  • num 不会包含任何前导零。

示例 1 :

1
2
3
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

1
2
3
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

1
2
3
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

题目详解

贪心。

  • 遍历字符串，每当当前字符大于他的下一个字符时，需要删除当前字符。
  • 可以实现一个单调栈（栈底到栈顶从小到大，不严格单调，可以相等）。
  • 注意长度为字符串原始长度减去 k。
  • 若有前导0，需要去掉（相应最终长度也会减小）。
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
public class LeetCode_00402 {

    public String removeKdigits(String num, int k) {
        if (k <= 0) {
            return num;
        }
        if (num.length() <= k) {
            return "0";
        }
        int len = num.length() - k;
        char[] cs = new char[num.length()];
        int top = -1;
        for (char c : num.toCharArray()) {
            while (top >= 0 && cs[top] > c && k > 0) {
                --top;
                --k;
            }
            cs[++top] = c;
        }
        // 去掉前导 '0'
        int offset = 0;
        while (offset <= top && cs[offset] == '0') {
            ++offset;
        }
        return offset > top ? "0" : new String(cs, offset, len - offset);
    }
}