带你读《图解算法小抄》十七、栈（10）

带你读《图解算法小抄》十七、栈（9）https://developer.aliyun.com/article/1348069?groupCode=tech_library

11.移除k位数字

给定一个非负整数字符串num和一个整数k，从该整数中移除k位数字，使得剩下的数字形成的整数尽可能小。返回移除k位数字后的结果。

示例：

输入：num = "1432219", k = 3 输出："1219" 解释：移除数字4、3和2后，剩下的数字形成的整数最小，即为1219。

输入：num = "10200", k = 1 输出："200" 解释：移除数字1后，剩下的数字形成的整数最小，即为200。

1）题目分析与解题步骤：

这个问题可以使用栈来解决。我们可以遍历整数字符串中的每个数字，然后使用一个栈来模拟移除数字的过程。对于每个数字，我们将其与栈顶元素比较，如果当前数字小于栈顶元素且还有剩余的移除次数k，则将栈顶元素出栈。最后，栈中的元素即为移除k位数字后的结果。

解题步骤如下：

创建一个栈stack，用于模拟移除数字的过程。

遍历整数字符串num中的每个数字，并执行以下操作：

将当前数字转换为整数类型。

如果栈不为空且当前数字小于栈顶元素且还有剩余的移除次数k，则将栈顶元素出栈，减少移除次数k。

将当前数字入栈。

如果移除次数k大于0，则从栈顶依次出栈，直到移除次数k减为0。

将栈中的元素按照出栈的顺序组合成字符串，并返回最终结果。

2）JavaScript解题框架：

function removeKDigits(num, k) {
  let stack = new Stack();
  for (let digit of num) {
    while (!stack.isEmpty() && digit < stack.peek() && k > 0) {
      stack.pop();
      k--;
    }
    stack.push(digit);
  }  while (k > 0) {
    stack.pop();
    k--;
  }
  let result = '';
  while (!stack.isEmpty()) {
    result = stack.pop() + result;
  }  // 移除前导零
  result = result.replace(/^0+/, '');  // 处理结果为空的情况
  if (result === '') {
    return '0';
  }
  return result;
}

在这个框架中，我们首先定义了一个栈类Stack，其中包含了常用的栈操作方法。然后，我们使用栈来移除k位数字。

在removeKDigits函数中，我们遍历整数字符串num，并使用栈来模拟移除数字的过程。对于每个数字，我们将其与栈顶元素比较，如果当前数字小于栈顶元素且还有剩余的移除次数k，则将栈顶元素出栈，减少移除次数k。

最后，我们将栈中的元素按照出栈的顺序组合成字符串，并返回最终结果。同时，我们需要处理结果为空的情况和移除前导零的情况。

带你读《图解算法小抄》十七、栈（11）https://developer.aliyun.com/article/1348066?groupCode=tech_library