当前位置：首页 > article >正文

LeetCode题练习与总结：移掉 K 位数字--402

article 2024/11/18 7:02:43

一、题目描述

给你一个以字符串表示的非负整数 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 不含任何前导零

二、解题思路

这个问题可以通过贪心算法和栈来解决。我们希望剩下的数字尽可能小，因此我们应该从左到右扫描数字，并且尽可能地保留较小的数字。具体步骤如下：

使用一个栈来保存最终的数字。
遍历输入的字符串数字。
对于当前数字，如果它小于栈顶元素，并且我们可以移除更多的数字（即 k > 0），那么我们就移除栈顶元素。这样可以保证栈中的数字始终是递增的，从而保证最后得到的数字是最小的。
如果当前数字大于或等于栈顶元素，或者 k 为 0，则将当前数字压入栈中。
遍历完成后，如果 k 仍然大于 0，则从栈顶移除额外的 k 个数字。
将栈中的数字转换为字符串，并去除前导零。
如果栈为空，则返回 “0”。

三、具体代码

import java.util.Stack;

class Solution {
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack<>();
        for (char c : num.toCharArray()) {
            // 当栈不为空，k大于0，并且栈顶元素大于当前元素时，弹出栈顶元素
            while (!stack.isEmpty() && k > 0 && stack.peek() > c) {
                stack.pop();
                k--;
            }
            // 当前字符不为'0'或者栈不为空时，将当前字符入栈
            if (c != '0' || !stack.isEmpty()) {
                stack.push(c);
            }
        }
        
        // 如果k还大于0，继续弹出栈顶元素
        while (!stack.isEmpty() && k > 0) {
            stack.pop();
            k--;
        }
        
        // 如果栈为空，返回"0"
        if (stack.isEmpty()) {
            return "0";
        }
        
        // 构建结果字符串
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        // 由于栈是逆序的，需要反转字符串
        return sb.reverse().toString();
    }
}

这段代码首先使用一个栈来维护一个递增的数字序列，然后通过遍历输入字符串，并按照贪心策略进行操作，最后将栈中的元素转换成字符串，并返回结果。注意，在构建结果字符串时，需要反转字符串，因为栈中保存的数字是逆序的。同时，在处理过程中，我们还要注意去除前导零。

四、时间复杂度和空间复杂度

1. 时间复杂度

遍历字符串 num 中的每个字符，需要 O(n) 的时间，其中 n 是字符串 num 的长度。
在每次遍历中，可能会进入一个循环，该循环会将栈顶元素弹出，直到不再满足条件。在最坏的情况下，这个循环可能执行 k 次。由于每次循环中都会减少 k 的值，因此这个循环总共最多执行 n 次（每个元素最多被弹出一次）。所以，这个循环对总时间复杂度的贡献是 O(n)。
最后，将栈中的元素转移到 StringBuilder 中，并反转字符串，这需要 O(n) 的时间。

综上所述，总的时间复杂度是 O(n) + O(n) + O(n) = O(n)，其中 n 是字符串 num 的长度。

2. 空间复杂度

使用了一个栈来存储数字，在最坏的情况下，如果 k 为 0，即不需要移除任何数字，那么栈中会存储所有的 n 个字符。因此，栈的空间复杂度是 O(n)。
使用了一个 StringBuilder 来构建最终的结果字符串，在最坏的情况下，它也会存储 n 个字符。因此，StringBuilder 的空间复杂度是 O(n)。

由于这两个数据结构是独立使用的，它们的空间复杂度是叠加的，因此总的空间复杂度是 O(n) + O(n) = O(n)，其中 n 是字符串 num 的长度。

五、总结知识点

数据结构 - 栈（Stack）：
- 栈是一种后进先出（LIFO）的数据结构，用于解决特定类型的问题，如括号匹配、逆序输出、函数调用等。
- 在这段代码中，栈用于维护一个递增的数字序列，从而帮助找到最小的数字。
贪心算法：
- 贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
- 在这个问题中，通过比较当前字符与栈顶字符，如果当前字符更小并且允许移除数字（k > 0），则移除栈顶字符，以保持剩余数字尽可能小。
字符串处理：
- 使用 toCharArray() 方法将字符串转换为字符数组，以便于遍历。
- 使用 StringBuilder 类来构建最终的字符串结果，这是因为 StringBuilder 在频繁修改字符串时比 String 更高效。
循环和条件判断：
- 使用 for 循环来遍历字符串中的每个字符。
- 使用 while 循环来处理栈操作，直到满足特定条件为止。
- 使用 if 语句和逻辑运算符来检查条件，如栈是否为空、k 是否大于 0 以及栈顶元素是否大于当前字符。
边界条件处理：
- 在将字符压入栈之前，检查字符是否为 ‘0’，以避免结果字符串中出现前导零。
- 在处理完所有字符后，如果 k 仍然大于 0，则继续从栈中移除元素，直到 k 为 0。
- 如果栈为空，则返回 “0”，这是处理特殊情况的一种方式，例如输入字符串全是 ‘0’ 或 k 等于字符串长度。