LeetCode 402 移掉K位数字

1.题目

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

2.题解

这道题是至今为止，我花费时间最多的一道题。回忆我走过的弯路，几乎是把能踩的坑都踩了一遍。第一个坑是移除K位数，K位，我这种较真的程序员就认定了是在字符串中连续的K个数，代码撸完美滋滋，一提交，报错。后来自己又写了一个大坑，就是用String字符串的toCharArray()方法来将String字符串转变为数组，这个就会有一个问题，就是在循环中我就自然使用了 nums[now+1]=nums[now]的写法用在了循环当中。循环本身是nums的长度，我们把这个长度看成是n;我就写了下面这段代码：

        char[] nums = num.toCharArray();
        int i=0;
        int now;
        while (k>0){
            now= i % length;
            char ch = num.charAt(now);
            if(nums[now+1]<nums[now]){
                //例：1下标的位置被0下标的数给替换了。
                nums[now] =nums[now+1];
                k--;
            }
            i++;
        }

结果就是：

image.png
But，这个代码是个啥？于是乎，我仔细又梳理了一遍，最终得偿所愿。
总结完了教训，我们来看看正儿八经的思路是什么样子的。
首先，我们是要去掉K位数，那么先把几种情况列明：
情况一：K<=0 . 返回 num;
情况二：length<=k||length==0。（length = num.length();） 返回 “0”
情况三：排除了情况一、二的其他情况。（主要讨论）
对于情况三，我们主要的思路就是用前一个比较后一个，下标0比较下标1，若前者比后者大则保留前者。否则继续比较。直至把K消耗殆尽。这样就得到了结果。
最后，在判断一下到底有没有前置0。若有n个0，则将取值的下标，往前移动n位即可。

3.代码

class Solution {
    public String removeKdigits(String num, int k) {
         //情况一：k=0
        if(k==0){
            return num;
        }
        //情况二：
        int length = num.length();
        int digits = length - k;
        if(length<=k||length==0){
            return "0";
        }
        //情况三：用K的个数来判断是否已经排除完了；
//        char[] nums = num.toCharArray();
        char[] result = new char[num.length()];
        int top=0;
        int i=0;
        // int now;
        while (i<num.length()){
            // now= i % length;
            char ch = num.charAt(i);
            while (top>0&&result[top-1]>ch&&k>0){
                k--;
                top--;
            }
            i++;//循环用的
            result[top++]=ch;
        }

        //下一步就是 去掉0
        int offset=0;
        while (offset<digits&&result[offset]=='0'){
           offset++;
        }
        //得到结果：
        return offset==digits?"0":new String(result,offset,digits-offset);
    }
}

4.结果截图

402.png