402.移掉K位数字

链接：402.移掉K位数字
难度：Medium
标签：栈、贪心、字符串、单调栈
简介：给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

题解 1 - typescript

• 编辑时间：2020-11-15
• 执行用时：104ms
• 内存消耗：41.2MB
• 编程语言：typescript
• 解法介绍：贪心，单调性，越小的数字在前面。

function removeKdigits(num: string, k: number): string {
  const stack: number[] = [];
  const isEmpty = () => stack.length === 0;
  for (const c of num) {
    const toNum = Number(c);
    if (isEmpty()) {
      stack.push(toNum);
    } else {
      let top = stack[stack.length - 1];
      while (toNum < top && k !== 0) {
        stack.pop();
        k--;
        top = stack[stack.length - 1];
      }
      stack.push(toNum);
    }
  }
  while (k-- !== 0) stack.pop();
  while (!isEmpty() && stack[0] === 0) stack.shift();
  return isEmpty() ? '0' : stack.join('');
}

题解 2 - typescript

• 编辑时间：2021-07-30
• 执行用时：92ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：单调栈。

function removeKdigits(num: string, k: number): string {
  const stack: number[] = [];
  for (let i = 0; i < num.length; i++) {
    const v = num.codePointAt(i)! - '0'.codePointAt(0)!;
    while (k && stack.length && stack[stack.length - 1] > v) {
      stack.pop();
      k--;
    }
    stack.push(v);
  }
  while (stack.length && k) {
    stack.pop();
    k--;
  }
  while (stack.length && stack[0] === 0) stack.shift();
  return stack.join('') || '0';
}