X

LEETCODE 402. Remove K Digits 解题思路分析

题目大意:

移掉K位数字

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

注意:

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

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=402

解题思路分析:

这道题目需要思考的点很多。试想要想得到剩下的数字最小,也就是说我们要删除掉高位上的较大数字。这是本题思想的核心部分,那么哪些数字是高位上较大的数字呢?比如数字213,虽然3是其中最大的数字,如果将它删除后可以得到数字21,但是显然删除2后得到的数字13更小。

逻辑上,我们从高位向低位循环,如果当前数字大于等于前一位上的数字,这时我们要是删除前一位的话,当前数字顶替到高位后只能使得数字变得更大(或者不变),因此此时我们将当前数字保留即可。反之如果当前数字小于前一位上的数字,说明在高位上存在较大的数,删除高位后,当前较小的数字即可顶替到它的位置,这样也就起到减少原数字的作用,同时,由于我们删除了一位数,此时的k值应该相应减一。当k为0时,说明我们无须再删除数字,剩下的所有数字都应该被保留。

解题时,我们使用Stack来保存剩下的数字,我们用当前位上的数字与Stack栈顶的数字进行比较,如果当前数字小于栈顶数字,则将栈顶数字pop出栈,同时k值减一。直到当前数字大于等于栈顶数字为止,然后将当前数字push入栈,并循环至下一个数字。这里需要注意一点,如果当前数字是0,并且栈中元素个数为空时,我们不能将该0插入到栈中,这个0实际上是返回结果的最高位,由于题目要求返回结果不能存在前导零,因此此时应该跳过。

循环结束之后,如果k值仍大于0,那么我们需要再删除一些数字。试想经过上述循环中的处理,当前Stack中的数字应该是一个非递减排序的列表(栈顶元素最大),我们只要从栈顶开始pop出栈k个元素即可。

最后我们再将Stack中剩下的元素拼接称为字符串返回。另外需要注意两点,首先,由于Stack中的元素是倒序出栈,因此,我们需要将其反向拼接才能组成正确的结果。另外,如果此时Stack的元素个数为0,直接返回0即可。

实现代码:

public String removeKdigits(String num, int k) {
    // 为了提高效率,先将字符串转为数组
    char[] arr=num.toCharArray();
    Stack<Character> s = new Stack<>();
    // 循环每个字符
    for(int i=0;i<num.length();i++){
        // 如果栈元素个数大于0并且k大于0,并且当前元素大于栈顶元素
        while(s.size()>0&&k>0&&arr[i]<s.peek()){
            s.pop(); // 栈顶元素pop出栈
            k--; // k减一
        }
        // 如果栈内元素个数为0,并且当前数字是0,跳过(前导零)
        if(s.size()==0&&arr[i]=='0') continue;
        // 将当前数字入栈
        s.push(arr[i]);
    }
    // 如果k仍大于0
    while(k>0&&s.size()>0){
        // 从栈顶pop出k个最大数
        s.pop();
        k--;
    }
    // 如果栈内元素个数为空,返回0
    if(s.size()==0) return "0";
    // 将栈内元素组成字符串返回
    StringBuilder sb=new StringBuilder();
    while(s.size()>0) sb.append(s.pop());
    sb.reverse();
    return sb.toString();
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 66.03% of Java online submissions for Remove K Digits.

Memory Usage: 40.2 MB, less than 9.09% of Java online submissions for Remove K Digits.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-402-remove-k-digits-解题思路分析/
Categories: leetcode
kwantong: