Vue.js

Appearance

On this page

实战：移掉 K 位数字 ​

给你一个数字字符串和一个整数 k，要移除 k 个数字使得剩下的数字最小。这道题用单调栈来贪心地选择要删除的数字。

问题描述 ​

LeetCode 402. Remove K Digits

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

示例：

输入：num = "1432219", k = 3
输出："1219"
解释：移除 4, 3, 2 得到最小的 1219

输入：num = "10200", k = 1
输出："200"

贪心策略 ​

从左到右扫描，如果当前数字比前一个数字小，就应该删除前一个数字。

为什么？因为高位的数字影响更大。例如 "143" 中删除 4 得到 "13"，比删除其他数字的结果都小。

解法：单调递增栈 ​

javascript
function removeKdigits(num, k) {
  const stack = [];
  
  for (const digit of num) {
    // 当前数字比栈顶小，弹出栈顶
    while (k > 0 && stack.length > 0 && digit < stack[stack.length - 1]) {
      stack.pop();
      k--;
    }
    stack.push(digit);
  }
  
  // 如果还没删够，从末尾删
  while (k > 0) {
    stack.pop();
    k--;
  }
  
  // 去除前导零
  let result = stack.join('').replace(/^0+/, '');
  
  return result || '0';
}

执行过程 ​

num = "1432219", k = 3

'1': stack = ['1']
'4': stack = ['1', '4']
'3': 3 < 4，弹出4，k=2，stack = ['1', '3']
'2': 2 < 3，弹出3，k=1，stack = ['1', '2']
'2': stack = ['1', '2', '2']
'1': 1 < 2，弹出2，k=0，stack = ['1', '2', '1']
'9': k=0，直接入栈，stack = ['1', '2', '1', '9']

结果："1219"

关键细节 ​

  1. k 用完就不删了：k > 0 的条件
  2. 删不够就从末尾删：递增序列时，删末尾的大数
  3. 去除前导零：结果可能有前导零
  4. 结果为空返回 "0"：全删完了

复杂度 ​

  • 时间：O(n)
  • 空间：O(n)

在 GitHub 上编辑此页