---

0402. 移掉 K 位数字

• 标签：栈、贪心、字符串、单调栈
• 难度：中等

题目链接

• 0402. 移掉 K 位数字 - 力扣

题目大意

描述：

给定一个以字符串表示的非负整数 $num$ 和一个整数 $k$。

要求：

移除这个数中的 $k$ 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

说明：

• $1 \le k \le num.length \le 10^{5}$。
• num 仅由若干位数字（$0 \sim 9$）组成。
• 除了 $0$ 本身之外，$num$ 不含任何前导零。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：贪心算法 + 单调栈

核心思想：要想让数字尽可能小，应该让高位尽可能小。从左到右遍历数字，如果当前数字比前面的数字小，则删除前面的数字可以让整体数字更小。

算法步骤：

1. 初始化单调栈 $stack$，用于维护一个从底到顶单调递增的数字序列。
2. 从左到右遍历字符串 $num$ 的每一位数字 $num[i]$：
   • 当栈不为空、$k > 0$ 且当前数字 $num[i] < stack[-1]$ 时，弹出栈顶元素并减少 $k$（贪心策略：删除高位较大的数字）。
   • 否则将当前数字压入栈中。
3. 如果 $k > 0$（还有需要删除的数字），则从栈底或栈顶继续删除 $k$ 位数字。
4. 去除前导零，将栈中剩余数字转换为字符串返回。

注意：需要处理以下边界情况：

• 如果所有数字都被删除完毕，返回 "0"。
• 返回结果需要去除前导零。

思路 1：代码

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        
        # 遍历字符串
        for digit in num:
            # 当前数字比栈顶小，删除栈顶（贪心）
            while stack and k > 0 and digit < stack[-1]:
                stack.pop()
                k -= 1
            stack.append(digit)
        
        # 如果还有剩余删除次数，从末尾删除
        if k > 0:
            stack = stack[:-k]
        
        # 去除前导零，转换为字符串
        result = ''.join(stack).lstrip('0')
        
        return result if result else '0'

思路 1：复杂度分析

• 时间复杂度：$O(n)$。其中 $n$ 是字符串 $num$ 的长度。每个数字最多进栈和出栈一次。
• 空间复杂度：$O(n)$。使用了一个栈存储数字，最坏情况下栈大小为 $n$。