What is the main strategy to remove k digits for minimal number?

The key is using a monotonic increasing stack: push digits and pop when the current digit is smaller, ensuring the smallest sequence.

How do I handle leading zeros after removing digits?

After building the number from the stack, strip all leading zeros. Return '0' if the string becomes empty.

Can this approach handle large inputs efficiently?

Yes, the stack-based approach processes each digit once, giving O(n) time and O(n) space, suitable for num.length up to 10^5.

What if k equals the length of num?

Removing all digits results in '0' as the output, which must be explicitly handled.

Why is this considered a stack-based state management problem?

Because maintaining the stack as an increasing sequence represents the current optimal state, allowing dynamic removal decisions while scanning the number.

#402

Medium

auto_awesome栈·状态

LeetCode 题解工作台

移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。示例 1 ：输入： num = "1432219", k = 3 输出： "1219" 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字…

字符串栈贪心单调栈

题目描述

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

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

提示：

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

lightbulb

解题思路

方法一：贪心算法

前置知识：两个相同位数的数字大小关系取决于第一个不同位的数的大小。

基本的思路如下：

从左到右遍历数组元素；
对于遍历到的当前元素，选择保留；
但可以选择性丢弃前面的相邻元素，丢弃与否取决于当前元素和前面相邻元素的大小；
根据前置知识可知当当前元素小于前面相邻元素时可以移除前面相邻的元素。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stk = []
        remain = len(num) - k
        for c in num:
            while k and stk and stk[-1] > c:
                stk.pop()
                k -= 1
            stk.append(c)
        return ''.join(stk[:remain]).lstrip('0') or '0'

speed

复杂度分析

指标	值
时间	complexity is O(n) since each digit is pushed and popped at most once in the stack. Space complexity is O(n) for storing the stack elements representing the partially built number.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if candidate identifies the need for a monotonic stack to maintain increasing digits.
question_mark
Observe whether they correctly remove digits when a higher digit precedes a smaller one.
question_mark
Verify handling of leading zeros and edge cases like complete removal of all digits.

warning

常见陷阱

外企场景

error
Removing digits without maintaining a monotonic stack can produce a non-minimal number.
error
Failing to handle leading zeros after removal may give incorrect output.
error
Not considering the case where k equals num.length results in missing the '0' return.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to remove k digits to form the largest possible integer instead.
arrow_right_alt
Restrict removals to contiguous segments instead of any digit positions.
arrow_right_alt
Introduce a cost per digit removed and find the minimal value respecting removal cost.

help

常见问题

外企场景

继续练习

#316 去除重复字母 #1081 不同字符的最小子序列 #321 拼接最大数