侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【单调栈】移掉 K 位数字

GabrielxD
2022-05-15 / 0 评论 / 0 点赞 / 29 阅读 / 914 字 / 正在检测是否收录...

题目

402. 移掉 K 位数字


给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k 位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 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 。

提示:

  • 1 <= k <= num.length <= 105
  • num 仅由若干位数字(0 - 9)组成
  • 除了 0 本身之外,num 不含任何前导零

解题

方法一:单调栈

思路

将问题“删除 k 位数字”转化为“保留 len - k 位数字”。

普遍的,对于两个数 $abc\underline{x}\square\square\square$ 和 $abc\underline{y}\square\square\square$:

  • 如果 $x>y$,则 $abcx\square\square\square > abcy\square\square\square$
  • 否则,$abcx\square\square\square \leq abcy\square\square\square$

得出结论:两个相同位数的数字大小关系取决于第一个不同的数的大小

维护一个单调栈(stack),栈中的元素代表截止到当前位置,删除不超过 k 次个数字后,所能得到的最小整数。 遍历字符串数字:

  • 如果 k > 0 且栈不为空且当前遍历到的数字 n 小于栈顶元素,不断地弹出栈顶元素,k自减。
  • 否则把栈顶元素入栈。

遍历完成后如果 k > 0 ,则需要把栈顶的 k 个元素出栈(删去多余数字)。 把栈中的字符全部出栈,并反向加入结果数字字符串。 如果结果数字字符串中存在前导零,则删除前导零。 此时如果结果数字字符串为空,则应该返回 "0" 否则返回结果数字字符串。

代码

class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) return "0";
        Deque<Character> stack = new LinkedList<>();
        for (char n : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && n < stack.peek()) {
                stack.pop();
                k--;
            }
            stack.push(n);
        }
        while (k-- > 0) stack.pop();
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.insert(0, stack.pop());
        }
        while (ans.indexOf("0") == 0) {
            ans.deleteCharAt(0);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}

优化

在把栈转为结果数字的过程中去除前导零,避免字符串操作。

class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) return "0";
        Deque<Character> deque = new LinkedList<>();
        for (char n : num.toCharArray()) {
            while (k > 0 && !deque.isEmpty() && n < deque.peek()) {
                deque.pop();
                k--;
            }
            deque.push(n);
        }
        while (k-- > 0) deque.pop();
        StringBuilder ans = new StringBuilder();
        boolean hasLeadingZero = true;
        while (!deque.isEmpty()) {
            char curr = deque.pollLast();
            if (hasLeadingZero && curr == '0') continue;
            hasLeadingZero = false;
            ans.append(curr);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}

优化

删去多余数字的操作也可以在把栈转为结果数字的过程中完成(从栈底部拉出 size - k 个元素,栈顶部就会留下多余的 k 个元素)。

class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) return "0";
        Deque<Character> deque = new LinkedList<>();
        for (char n : num.toCharArray()) {
            while (k > 0 && !deque.isEmpty() && n < deque.peek()) {
                deque.pop();
                k--;
            }
            deque.push(n);
        }
        StringBuilder ans = new StringBuilder();
        boolean hasLeadingZero = true;
        while (deque.size() > k) {
            char curr = deque.pollLast();
            if (hasLeadingZero && curr == '0') continue;
            hasLeadingZero = false;
            ans.append(curr);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}
0

评论区