【LeetCode-402】402.移除k位数字（给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。）

移除k位数字

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

在这里插入图片描述

思路：单调栈（贪心+栈）

class Solution {
    
    /*
    单调栈的另一个应用，思想为删除靠前的较大的数能够使得最后的数值最小。 构建递增栈，若当前数字小于栈顶元素，则在满足待删减字符数不为0的情况下，栈顶元素出栈，当前数字入栈。
    */
    public String removeKdigits(String num, int k) {
         //贪心算法+单调栈
        if(k >= num.length() || num.length() == 0) {
            return "0";
        }
        //栈顶始终是最大值    
        Stack<Integer> stack = new Stack<>();
        stack.push(num.charAt(0) - '0');
        
        for(int i = 1; i < num.length() ; i++) {
            int now = num.charAt(i) - '0';
            //可能好几个值都比当前值大，那么我们就在k允许的情况下，去去除它。
            while(!stack.isEmpty() && stack.peek() > now && k > 0) {
                stack.pop();
                k--;
            }
            //不等于0可以添加进去,
            //等于0，栈不为空可以填进去，
            if(now != 0 || !stack.isEmpty()) {
                stack.push(now);
            }
            
        }
        
        //56789这种情况，前面一直比后面小，那就去除栈顶，谁让栈顶最大
        while(k > 0) {
            k--;
            stack.pop();
        }
        
        //10，1(当now=0时，满足条件，去掉1，但now为0，且为空。)
        if(stack.isEmpty()) {
            return "0";
        }
        
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()) {
            res.append(stack.pop());
        }
        
        //从后往前添加,所以我们要逆序
        return res.reverse().toString();
    }
    
}

扩展：相似的题

321.拼接最大数

本文链接：https://blog.csdn.net/weixin_42956047/article/details/106364279

智能推荐

CentOS7引导Windows7

简单说下吧一开始是直接在 boot/grub2/grub.cfg里作如下变动：找到 ### BEGIN /etc/grub.d/30_os-prober ###，在后面添加 grub2从1计数，win7装在C盘上的(可以在终端里输入 fdisk -l 来确定下，一般win都是装在C的吧) OK,保存后，启动画面里出现了win7的选项接下来是修改等待时间和默认启动项这里有个问题，...

尚硅谷2020周阳老师SpringCloud学习整理笔记第二部分

第一部分：尚硅谷周阳老师SpringCloud学习整理笔记第一部分经过5天的学习，目前学到了P92,刚刚结束了SpringCloud Stream,由于还有一些别的事情所以进度有点慢，笔记也整理得有点潦草。第一部分篇幅逐渐臃肿，故下面的笔记，分享于这篇博客。笔记供自己日后复习，若有需要也供大家参考。若有不足，还请指正。十三、Hystrix Hystrix介绍在微服务场景中，通常会有很多层的...

准备在天池新人赛中使用随机森林。网上搜索了一个博客： http://blog.csdn.net/lulei1217/article/details/49583287 下面是自己实现的代码： from sklearn.tree import DecisionTreeRegressor from sklearn.ensemble import RandomForestRegressor import...

如何用FPGA产生PWM波形（增减计数器模式设计）

之前做电机控制都是用DSP产生不同占空比的PWM波形，但是由于项目需要，要用FPGA产生不同占空比的PWM波形，通过查阅资料看到不少的方式方法，综合了一下，按着自己的思路写了一个产生6路3对PWM 波形，并且仿真和实测都满足设计要求。通常情况下我们的思路是设计一个计数器，增加到一定要求然后置零，往复循环即可，但是，这次有一个问题，为了让达到与DSP的计数模式一致，我们需要设计这个计数器，它先递增...

数据结构10:队列抽象数据类型

一、什么队列队列是有次序的数据集合，其特征是：新数据项的添加总发生在一端，通常称为“尾rear端” 现存数据的一处总发生在另一端，通常称为“首front端” 当数据项加入队列时，首先出现在队尾，随着队首数据项的移除，它逐渐接近队首。新加入的数据项必须在数据集的末尾等待，而等待时间最长的数据项则是队首，这种次序安排的原则称为FIFO(First-i...