LeetCode - 402 移掉 K 位数字

r囧r小猫 2023-09-24 12:47 49阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[402. 移掉 K 位数字 - 力扣（LeetCode）][402. _ K _ - _LeetCode]

### 题目描述 ###

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

### 示例 ###

> 输入：num = "1432219", k = 3  
> 输出："1219"  
> 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

> 输入：num = "10200", k = 1  
> 输出："200"  
> 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

> 输入：num = "10", k = 2  
> 输出："0"  
> 解释：从原数字移除所有的数字，剩余为空就是 0 。

### 提示 ###

*  `1 <= k <= num.length <= 105`
 *  `num` 仅由若干位数字（0 - 9）组成
 *  除了 **0** 本身之外，`num` 不含任何前导零

### 题目解析 ###

此题和[算法 - 找最小数\_伏城之外的博客-CSDN博客][- _-CSDN]

类似，我们需要返回一个有顺序要求的最小数，因此可以使用栈结构来维持顺序性。

比如输入为“1022”，移除2位，求最小数。

我们可以创建一个栈，然后遍历输入字符串1022的每一个数字，尝试压入栈中：

1、在压入栈前，需要判断栈顶是否有元素，如果没有元素，则直接压入，例如1入栈时发现栈是空的，因此直接入栈，此时栈：\[1\]

2、如果栈顶有元素，则比较遍历的数字和栈顶数字，如果遍历的数字更小，则将栈顶元素弹栈，并压入遍历出来的数字。由于有元素被弹栈，表示移除了一位，因此剩余只需要移除一位就可以结束了

经过上面两步栈中元素为：\[0,2,2\]

即上面两个步骤是保留至少 num.length - k 个 原输入字符串中的最小数字。

3、如果此时栈深度大于num.length - k，因此，我们需要将栈顶较大值给pop出去，直到栈深度等于num.length - k,此时栈：\[0,2\]

4、到此我们还应该考虑前导0的问题，判断栈底元素是否为0，若为0，则判断栈深度是否为1，即判断栈中是否只有一个0元素，此时我们应该输出“0”。若栈深度大于1，则需要shift出栈底0.

### 算法源码 ###

/**
     * @param {string} num
     * @param {number} k
     * @return {string}
     */
    var removeKdigits = function(num, k) {
        if(k === num.length) return "0"
    
        let stack = []
        let remain = num.length - k
    
        for(let i=0; i<num.length; i++) {
            while(stack.length > 0 && k > 0 && stack[stack.length - 1] > num[i]) {
                stack.pop()
                k--
            }
            stack.push(num[i])
        }
    
        while(stack.length > remain) {
            stack.pop()
        }
    
        while(stack[0] === '0' && stack.length !== 1) {
            stack.shift()
        }
    
        return stack.join('')
    };

![e1bb2e6cfa35404697c34c7b3cca8e7f.png][]

[402. _ K _ - _LeetCode]: https://leetcode.cn/problems/remove-k-digits/
[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127342038?spm=1001.2014.3001.5501
[e1bb2e6cfa35404697c34c7b3cca8e7f.png]: https://img-blog.csdnimg.cn/e1bb2e6cfa35404697c34c7b3cca8e7f.png