LeetCode 402. 移掉 K 位数字

Categories:

Tags:

题目描述
思路分析
参考代码
相似题目

题目描述

🔥 402. 移掉 K 位数字

思路分析

为了使剩下的数字最小，我们可以使用一个栈来解决这个问题。具体步骤如下：

初始化一个空栈，用于存储最终结果的数字。

遍历字符串 num 中的每一个字符 digit。

在遍历过程中，如果栈不为空且栈顶元素大于当前字符 digit，并且 k 大于 0，则弹出栈顶元素，并将 k 减 1。

将当前字符 digit 压入栈中。

如果遍历结束后 k 仍然大于 0，则从栈顶开始弹出 k 个元素。

最后，将栈中的元素拼接成字符串，并去掉前导零。

参考代码

func removeKdigits(num string, k int) string {
	var stack []byte

	for i := 0; i < len(num); i++ {
		digit := num[i]
		for len(stack) > 0 && k > 0 && stack[len(stack)-1] > digit {
			stack = stack[:len(stack)-1]
			k--
		}
		stack = append(stack, digit)
	}

	// 如果 k 仍然大于 0，继续从栈顶弹出元素
	stack = stack[:len(stack)-k]

	// 去掉前导零
	res := ""
	leadingZero := true
	for _, digit := range stack {
		if leadingZero && digit == '0' {
			continue
		}
		leadingZero = false
		res += string(digit)
	}

	if res == "" {
		return "0"
	}
	return res
}

时间复杂度：O (n)，其中 n 是字符串 num 的长度。每个字符最多被压入和弹出栈一次。

空间复杂度：O (n)，用于存储栈的空间。

write your code here

🍏 点击查看 Java 题解

write your code here

相似题目

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/70730153