LeetCode 402. 移掉 K 位数字

Categories:

Tags:

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

题目描述

✅ 402. 移掉 K 位数字

思路分析

单调递增栈

参考代码

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

    for i := 0; i < len(num); i++ {
        // 当栈不为空，且当前数字小于栈顶数字，并且还有可以移除的数字
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
            stack = stack[:len(stack)-1] // 弹出栈顶元素
            k--
        }
        stack = append(stack, num[i]) // 将当前数字推入栈中
    }

    // 如果还有剩余的 k，移除栈末尾的元素
    for k > 0 {
        stack = stack[:len(stack)-1]
        k--
    }

    // 将栈中的数字拼接成字符串
    res := string(stack)

    // 去掉前导零
    for len(res) > 0 && res[0] == '0' {
        res = res[1:]
    }

    // 如果结果为空，返回 "0"
    if res == "" {
        return "0"
    }

    return res
}

func removeKdigits(num string, k int) string {
	var stack []byte
	for i := 0; i < len(num); i++ {
		// 若当前数字比栈顶数字小，移除栈顶元素
		for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
			stack = stack[:len(stack)-1]
			k--
		}
		stack = append(stack, num[i])
	}

	// 如果还有需要移除的数字
	for k > 0 {
		stack = stack[:len(stack)-1]
		k--
	}

	// 移除前导零
	res := string(stack)
	i := 0
	for i < len(res) && res[i] == '0' {
		i++
	}
	res = res[i:]

	if len(res) <= 0 {
		return "0"
	}

	return res
}