402. 移掉 K 位数字

🟠   🔖  栈 贪心 字符串 单调栈  🔗 力扣 LeetCode

题目

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits fromnum.

Example 1:

Input: num = "1432219", k = 3

Output: "1219"

Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1

Output: "200"

Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2

Output: "0"

Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

• 1 <= k <= num.length <= 10^5
• num consists of only digits.
• num does not have any leading zeros except for the zero itself.

题目大意

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

示例 1 ：

输入： num = "1432219", k = 3

输出： "1219"

解释： 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：

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

输出： "200"

解释： 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：

输入： num = "10", k = 2

输出： "0"

解释： 从原数字移除所有的数字，剩余为空就是 0 。

提示：

• 1 <= k <= num.length <= 10^5
• num 仅由若干位数字（0 - 9）组成
• 除了 0 本身之外，num 不含任何前导零

解题思路

• 贪心策略 + 单调栈
  • 使用单调递增栈存储候选数字，确保栈中元素构成的数最小。
  • 遍历字符串 num 时，遇到比栈顶元素更小的数字，将栈顶元素弹出以获得更小的结果。

1. 维护单调栈：
   • 遍历 num，当栈不为空、k > 0 且当前字符小于栈顶时弹出栈顶，并减少 k。
2. 处理剩余移除需求：
   • 若 k > 0，说明字符串 num中递增的数字超过所需个数，从栈尾继续移除 k 个字符。
3. 去除前导零：
   • 使用 shift() 去掉栈中多余的前导零。
4. 返回结果：
   • 若栈为空返回 "0"，否则返回拼接后的数字字符串。

复杂度分析

• 时间复杂度：O(n)，遍历字符串一次并维护栈操作。
• 空间复杂度：O(n)，栈的空间消耗。

代码

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function (num, k) {
	let stack = [];
	for (let char of num) {
		while (stack.length > 0 && k > 0 && stack[stack.length - 1] > char) {
			stack.pop();
			k--;
		}
		stack.push(char);
	}

	// 如果 k 还大于 0，从末尾继续删除
	stack = stack.slice(0, stack.length - k);

	// 去除前导零
	while (stack[0] === '0') {
		stack.shift();
	}

	return stack.length > 0 ? stack.join('') : '0';
};

相关题目

题号	标题	题解	标签	难度	力扣
321	拼接最大数		栈 贪心 数组 2+	🔴	🀄️ 🔗
738	单调递增的数字		贪心 数学	🟠	🀄️ 🔗
1673	找出最具竞争力的子序列		栈 贪心 数组 1+	🟠	🀄️ 🔗
2195	向数组中追加 K 个整数		贪心 数组 数学 1+	🟠	🀄️ 🔗
2259	移除指定数字得到的最大结果	[✓]	贪心 字符串 枚举	🟢	🀄️ 🔗
2844	生成特殊数字的最少操作		贪心 数学 字符串 1+	🟠	🀄️ 🔗