跳至主要內容

LeetCode 402. 移掉K位数字——单调栈贪心构造最小数

老张2026/4/30大约 6 分钟

LeetCode 402. 移掉K位数字——单调栈贪心构造最小数

适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约20分钟 | 难度：中等

开篇故事

这道题我特别喜欢拿来和上一篇的 316「去除重复字母」放在一起对比讲，因为两题思路高度相似，但约束条件不同，导致代码结构有细微但关键的差异。

316 是「每种字符只留一个，字典序最小」，约束是字符种类。402 是「总共删掉 k 个数字，剩余数字组成的数最小」，约束是删除次数。

理解了这两道题，再看 321「拼接最大数」就会有豁然开朗的感觉。

一、题目解析

题目描述：

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

示例：

输入：num = "1432219", k = 3
输出："1219"

输入：num = "10200", k = 1
输出："200"（注意前导零处理）

输入：num = "10", k = 2
输出："0"

约束：

  • 1 <= k <= num.length <= 10^5
  • num 不包含除前导零以外的前置零

核心理解： 想让剩余数最小，高位的数字越小越好。贪心策略：从左到右扫描，如果当前数字比前一个数字小，就把前一个数字删掉（消耗一次删除机会）。

二、解法一：暴力递归

思路分析

每次从数字中选择一个删除位置，使剩余数字最小，重复 k 次。

class Solution {
    public String removeKdigits(String num, int k) {
        String s = num;
        for (int i = 0; i < k; i++) {
            s = removeOne(s);
        }
        // 去除前导零
        int start = 0;
        while (start < s.length() - 1 && s.charAt(start) == '0') start++;
        return s.substring(start);
    }
    
    // 移除一个数字使结果最小
    private String removeOne(String s) {
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) > s.charAt(i + 1)) {
                // 移除 i 位置的数字
                return s.substring(0, i) + s.substring(i + 1);
            }
        }
        // 已经是递增序列，移除最后一个
        return s.substring(0, s.length() - 1);
    }
}

复杂度分析

  • 时间复杂度：O(k × n)。每次删除操作 O(n)，共 k 次。最坏 O(n²)。
  • 空间复杂度：O(n)。

三、解法二：优先队列每次找最优删除点

思路分析

另一个角度：从 n 个数字中选 n-k 个，使组成的数字最小，且保持原有相对顺序。这变成了一个「从序列中按序选 m 个元素使结果最小」的问题。

class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length();
        int m = n - k; // 要保留的数字个数
        
        if (m == 0) return "0";
        
        char[] result = new char[m];
        int start = 0; // 下一次选择的起点
        
        for (int i = 0; i < m; i++) {
            // 在 [start, n-(m-i)+1) 范围内找最小的数字
            int end = n - (m - i - 1); // 保证后面还有足够的数字
            int minIdx = start;
            for (int j = start + 1; j < end; j++) {
                if (num.charAt(j) < num.charAt(minIdx)) {
                    minIdx = j;
                }
            }
            result[i] = num.charAt(minIdx);
            start = minIdx + 1;
        }
        
        // 构建结果，去除前导零
        StringBuilder sb = new StringBuilder();
        boolean leadingZero = true;
        for (char c : result) {
            if (leadingZero && c == '0') continue;
            leadingZero = false;
            sb.append(c);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

复杂度分析

  • 时间复杂度：O(n²)。外层循环 m 次，内层扫描 O(n)。
  • 空间复杂度：O(n)。

四、解法三（最优）：单调栈贪心

核心思想

贪心策略：维护一个单调递增栈（栈底到栈顶非递减）。

遍历数字字符串：

  1. 当前数字 c 比栈顶 top 小，且删除次数 k > 0：弹出 top（相当于删除 top），k--
  2. 重复步骤1直到栈为空、k=0 或栈顶 <= c
  3. 将 c 入栈

遍历结束后，如果 k > 0，删除栈顶 k 个元素（此时栈是递增的，栈顶最大）。

最后处理前导零，构建结果。

完整代码

import java.util.*;

class Solution {
    public String removeKdigits(String num, int k) {
        // 单调递增栈（存字符）
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : num.toCharArray()) {
            // 当前数字比栈顶小，且还有删除次数，就弹出栈顶
            while (k > 0 && !stack.isEmpty() && stack.peek() > c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        
        // 如果还有删除次数，删掉末尾（栈顶是最大的）
        while (k > 0) {
            stack.pop();
            k--;
        }
        
        // 构建结果
        StringBuilder sb = new StringBuilder();
        // stack 是头插，遍历是从栈顶到栈底（逆序），需要反转
        for (char c : stack) sb.append(c);
        sb.reverse();
        
        // 去除前导零
        int start = 0;
        while (start < sb.length() - 1 && sb.charAt(start) == '0') start++;
        
        return sb.substring(start);
    }
}

手动模拟

以 num = "1432219", k = 3 为例：

字符k操作栈（栈底→栈顶）
13入栈[1]
434>1 不弹，入栈[1,4]
334>3 弹4(k=2)，1<3 不弹，入栈[1,3]
223>2 弹3(k=1)，1<2 不弹，入栈[1,2]
212>=2 不弹，入栈[1,2,2]
112>1 弹2(k=0)，不再弹，入栈[1,2,1]
90k=0 不弹，入栈[1,2,1,9]

最终栈（反转后）：1,2,1,9 → "1219"，正确！

复杂度分析

  • 时间复杂度：O(n)。每个字符最多入栈出栈各一次。
  • 空间复杂度：O(n)。

五、举一反三

题目相似点区别
316. 去除重复字母贪心+单调栈约束是每种字符只出现一次
321. 拼接最大数贪心选子序列两数组各取部分拼接
1673. 找到最具竞争力的子序列几乎与402相同保留k个而非删除k个

六、踩坑实录

坑一：遍历结束后 k > 0 时忘记继续删除

如果数字是单调递增的（比如 12345，k=2），遍历完栈不会弹任何元素，k 还是 2。这时候必须删掉栈顶 k 个元素（递增栈的末尾，即最大的那些）。

// 遍历完后的收尾处理，容易忘
while (k > 0) {
    stack.pop();
    k--;
}

坑二：前导零处理

"10200" 删掉1个得 "0200"，前导零需要去掉变成 "200"。但如果全是零，比如 "0"，不能返回空字符串，要返回 "0"。

所以去零时保留最后一个字符的逻辑要小心：

int start = 0;
// 最后一个字符不跳（length-1 是边界）
while (start < sb.length() - 1 && sb.charAt(start) == '0') start++;

坑三：当 k >= num.length() 时

题目保证 k <= num.length。如果 k == num.length，所有数字都删掉，返回 "0"。这种情况在代码里会自然处理：栈会被清空，然后 sb 是空的，start = 0，sb.substring(0) 是空字符串，但因为 start < sb.length()-1 的边界判断，实际上 sb.length()-1=-1 时会直接返回空。

最好显式处理：

if (k >= num.length()) return "0";

七、总结

402 和 316 是同一类题的不同约束版本，核心思路都是「单调栈贪心」，但关键细节不同：

  • 316 有「每种字符恰好出现一次」的约束，需要 inStack 数组和 remain 计数
  • 402 有「总删除次数 k」的约束，需要维护 k 的消耗

收尾处理也不同：316 反转输出，402 还需要处理前导零。

这两道题放在一起对比学习效果最好，建议同时做一遍，感受约束条件变化对代码的影响。

编辑此页
最近更新:
贡献者: xiaozhangge