LeetCode 402. 移掉 K 位数字

Categories:

题目描述
思路分析
1. 解法一：单调栈贪心（推荐）
相似题目

题目描述

✅ 402. 移掉 K 位数字

思路分析

解法一：单调栈贪心（推荐）

核心思路：

维护单调递增栈，保证结果字典序最小。

遇到更小数字时弹出栈顶并减少 k。

最后若 k 仍大于 0，继续从末尾删除。

去除前导零，若为空返回 “0”。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，用于栈或结果数组。

import java.util.*;

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();

        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            while (k > 0 && !stack.isEmpty() && stack.peekLast() > c) {
                stack.pollLast();
                k--;
            }
            stack.addLast(c);
        }

        while (k > 0 && !stack.isEmpty()) {
            stack.pollLast();
            k--;
        }

        StringBuilder sb = new StringBuilder();
        boolean leadingZero = true;
        while (!stack.isEmpty()) {
            char c = stack.pollFirst();
            if (leadingZero && c == '0') {
                continue;
            }
            leadingZero = false;
            sb.append(c);
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }
}

func removeKdigits(num string, k int) string {
	stack := make([]byte, 0)

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

	for k > 0 && len(stack) > 0 {
		stack = stack[:len(stack)-1]
		k--
	}

	res := make([]byte, 0)
	leadingZero := true
	for _, c := range stack {
		if leadingZero && c == '0' {
			continue
		}
		leadingZero = false
		res = append(res, c)
	}

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

相似题目

题目	难度	考察点
316. 去除重复字母	中等	单调栈
321. 拼接最大数	困难	贪心
1673. 找出最具竞争力的子序列	中等	单调栈
670. 最大交换	中等	贪心
402. 移掉 K 位数字	中等	单调栈

本文作者: HGNULB

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