带你读《图解算法小抄》十七、栈(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