移掉 K 位数字

移掉 K 位数字

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

解题思路

首先我们要了解一个关于数学的前置知识,对于两个相同长度的数字序列,最左边不同的数字决定了这两个数字的大小,例如,对于 A = 1axxxA = 1axxx,B = 1bxxxB = 1bxxx,如果 a > b,则 A > B

基于此,我们可以知道,若要使得剩下的数字最小,需要保证靠前的数字尽可能小

如果使用暴力法,那思路就是:

  • 从左到右遍历
  • 对于每一个遍历到的元素,前一个元素比当前元素大,则丢弃前一个元素,否则保留前一个元素

需要注意的是,如果给定的数字是一个单调递增的数字,那么我们的算法会永远选择不丢弃。这个题目中要求的,我们要永远确保丢弃 k 个数字,因此思路还应该稍加修改:

  • 每次丢弃一次,k 减去 1。当 k 减到 0 ,我们可以提前终止遍历
  • 而当遍历完成,如果 k 仍然大于 0。不妨假设最终还剩下 x 个需要丢弃,那么我们需要选择删除末尾 x 个元素

然而暴力的实现复杂度最差会达到 O(nk)(考虑整个数字序列是单调不降的),因此我们需要加速这个过程

可以用一个栈维护当前的答案序列,栈中的元素代表截止到当前位置,删除不超过 k 次个数字时,所能得到的最小整数。根据之前的讨论:在使用 k 个删除次数之前,栈中的序列从栈底到栈顶单调不降。因此,对于每个数字,如果该数字小于栈顶元素,我们就不断地弹出栈顶元素,直到

  • 栈为空
  • 新的栈顶元素不大于当前数字
  • 已经删除了 k 位数字

上述步骤结束后我们还需要针对一些情况做额外的处理:

  • 如果我们删除了 m 个数字且 m<k,我们需要从序列尾部删除额外的 k-m 个数字
  • 如果最终的数字序列存在前导零,我们要删去前导零
  • 如果最终数字序列为空,我们应该返回 0
class Solution {

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/2599.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 压力换算公斤单位换算_压力单位换算表

    压力换算公斤单位换算_压力单位换算表压力单位换算表来源:华强电子网作者:华仔浏览:1163时间:2016-08-1014:18标签:摘要:november6,2002牛顿/米2(帕斯卡)(n/m2)(pa)公斤力/米2(kgf/m2)公斤力/厘米2(kgf/cm2)巴(bar)标准大气压(atm)毫米水柱4oc(mmh2o)毫米水银柱0oc(mmhg)磅/英寸2(lb/in2,psi)牛顿/米2(帕斯卡)(n…

  • docker端口映射无法外部访问_docker用户映射

    docker端口映射无法外部访问_docker用户映射端口映射容器中可以运行一些应用,要让外部也可以访问这些应用,可以通过-P或-p参数来指定端口映射。当使用大写的-P标记时,Docker会随机映射一个物理机的49000~49900之间的端口到内部容器开放的网络端口。-p则可以指定想要映射的物理机端口,并且,在一个指定端口上只可以绑定一个容器。1.映射指定的本地IP和端口到容器端口dockerrun-it-p192.168.10.10:8000:80busybox2.映射本地指定IP的任意端口到

    2022年10月18日
  • Navicat Premium 15安装需要注意的几个细节

    Navicat Premium 15安装需要注意的几个细节关于软件的下载和激活的流程,网上有太多文章了,这里就不赘述了。主要记录几个细节问题:安装完NavicatPremium15后,激活之前一定不要打开它!打开它不一定有问题,但可以尽量避免后面的各种错误。 下载完成之后,安装解压的过程尽量在断网的情况下进行!不断网不一定有问题,但可以尽量避免后面出现各种问题!激活的过程中,如果没注意这两种,那可能就是经历什么rsapublickeynotfind,或者输入激活密钥有个红叉号等等各种各样的问题,为了避免一些不必要的麻烦,还是按顺序来吧,希望看到

  • 什么叫构造方法?_构造方法和普通方法之间的区别

    什么叫构造方法?_构造方法和普通方法之间的区别构造方法是一种特殊的方法,它是一个与类同名且没有返回值类型的方法。对象的创建就是通过构造方法来完成,其功能主要是完成对象的初始化。当类实例化一个对象时会自动调用构造方法。构造方法和其他方法一样也可以重

  • 数组和集合的相互转换「建议收藏」

    数组和集合的相互转换「建议收藏」数组和集合的相互转换

  • LaTeX学习:Texlive 2019和TeX studio的安装及使用「建议收藏」

    LaTeX学习:Texlive 2019和TeX studio的安装及使用「建议收藏」文章目录1.LaTex介绍2.Texlive2019的下载和安装(1)下载(2)安装3.TeXstudio的安装以及简单使用(1)设置中文界面(2)添加行号(3)设置编译器与编码(4)第一个简单程序4.扩展1.LaTex介绍LaTeX基于TeX,主要目的是为了方便排版。在学术界的论文,尤其是数学、计算机等学科论文都是由LaTeX编写,因为用它写数学公式非常漂亮。…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号