402. 移掉 K 位数字

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

示例 1 ：

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

示例 2 ：

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

示例 3 ：

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

解题思路

核心思路是单调栈 + 贪心算法，通过维护一个递增的栈来确保剩余数字最小，同时控制移除的数字数量不超过 k：

  1. 单调栈逻辑：
    • 遍历字符串中的每个数字，对于当前数字c：
      • 若栈不为空，且栈顶数字大于 c，且仍有可移除的次数（k > 0），则弹出栈顶数字（移除该数字可使结果更小），同时 k--；
      • 将当前数字 c 压入栈。
  2. 处理剩余可移除次数：
    • 若遍历结束后 k 仍大于 0（说明剩余数字是递增的），则从栈尾移除 k 个数字。
  3. 清理前导零和空字符串：
    • 移除栈中开头的所有 '0'（避免前导零）；
    • 若栈为空，返回 "0"，否则返回栈中字符组成的字符串。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<char> stack;  // 用vector模拟栈，便于处理
        
        for (char c : num) {
            // 栈非空，栈顶数字大于当前数字，且还有可移除次数
            while (!stack.empty() && k > 0 && stack.back() > c) {
                stack.pop_back();  // 移除栈顶数字
                k--;
            }
            stack.push_back(c);  // 当前数字入栈
        }
        
        // 若还有剩余可移除次数，从栈尾移除
        while (k > 0 && !stack.empty()) {
            stack.pop_back();
            k--;
        }
        
        // 移除前导零
        int start = 0;
        while (start < stack.size() && stack[start] == '0') {
            start++;
        }
        
        // 构建结果
        string result;
        for (int i = start; i < stack.size(); ++i) {
            result += stack[i];
        }
        
        // 若结果为空，返回"0"，否则返回结果
        return result.empty() ? "0" : result;
    }
};