402.移掉K位数字

题目描述

给你一个以字符串表示的非负整数 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. 从左到右遍历数字，使用栈维护一个单调递增的序列
2. 当遇到一个数字比栈顶元素小时，且还有可以移除的次数(k>0)时，移除栈顶元素
3. 重复步骤2直到不能再移除或者栈为空
4. 处理特殊情况（前导零、k仍大于0等）

简洁优化版本

class Solution {
    func removeKdigits(_ num: String, _ k: Int) -> String {
        // 特殊情况处理
        guard k < num.count else { return "0" }
        guard k > 0 else { return num }
        
        // 初始化栈和计数器
        var stack = [Character]()
        var remain = k
        
        for char in num {
            // 对于每个新数字，我们都要和栈顶元素比较
            while let last = stack.last,  // 获取栈顶元素
                  last > char,            // 栈顶元素比当前数字大
                  remain > 0 {            // 还有可以删除的次数
                stack.removeLast()        // 移除栈顶元素
                remain -= 1               // 可删除次数减1
            }
            stack.append(char)            // 将当前数字入栈
        }
        
        // 处理未使用完的k
        stack.removeLast(remain)
        
        // 移除前导零并构建结果
        let result = String(stack).drop { $0 == "0" }
        return result.isEmpty ? "0" : String(result)
    }
}

代码说明

1. 特殊情况处理：

   guard k < num.count else { return "0" }
   guard k > 0 else { return num }
   

   • 如果k大于等于字符串长度，返回”0”
   • 如果k为0，直接返回原字符串
2. 栈的初始化：

   var stack = [Character]()
   var remain = k
   

   • 使用Character数组作为栈
   • remain记录还需要删除的数字个数
3. 核心逻辑：

   while let last = stack.last,
         last > char,
         remain > 0 {
       stack.removeLast()
       remain -= 1
   }
   

   • 使用可选绑定安全地获取栈顶元素
   • 多条件判断更加清晰
   • 当栈顶元素大于当前数字时移除
4. 后处理：

   stack.removeLast(remain)
   let result = String(stack).drop { $0 == "0" }
   return result.isEmpty ? "0" : String(result)
   

   • 一次性移除剩余需要删除的数字
   • 使用drop优雅地处理前导零
   • 使用三元运算符处理空结果

优化说明

1. 代码简化：
   • 使用guard语句处理特殊情况
   • 使用可选绑定和多条件判断
   • 使用Swift的高阶函数特性
2. 性能优化：
   • 减少类型转换
   • 使用Character而不是Int存储
   • 使用removeLast(n)批量删除
3. 安全性提升：
   • 使用可选绑定避免强制解包
   • 处理所有边界情况
   • 确保返回值的正确性

这个版本的代码更加简洁易读，同时保持了良好的性能和安全性。通过详细的注释，使得代码的意图和实现方式更加清晰。

代码分析

1. 边界条件处理：
   • 如果k大于等于字符串长度，直接返回”0”
   • 最后如果结果为空，返回”0”
2. 核心逻辑：
   • 使用栈来维护结果
   • 遍历每个数字时，与栈顶元素比较
   • 当前数字小于栈顶元素且还能移除数字时，移除栈顶元素
3. 后处理：
   • 处理剩余的k（从末尾移除）
   • 移除前导零
   • 处理空栈情况

复杂度分析

• 时间复杂度：O(n)，其中 n 是数字字符串的长度。虽然有嵌套的循环，但每个字符最多被压入和弹出栈一次。
• 空间复杂度：O(n)，需要一个栈来存储中间结果。

算法优化思考

1. 提前返回：
   • 当k等于字符串长度时可以提前返回
   • 当字符串只包含一个字符时可以简化处理
2. 内存优化：
   • 可以使用字符数组代替栈，减少内存分配
   • 可以直接在原字符串上操作（如果允许修改输入）
3. 性能优化：
   • 可以在移除前导零的同时构建结果字符串
   • 可以使用StringBuilder类型的数据结构来提高字符串操作效率

总结

这道题展示了单调栈的经典应用，通过维护栈的单调递增特性来找到最优解。关键点在于：

1. 理解单调栈的思想：维护递增序列，较大数字会被弹出
2. 使用栈来维护单调性
3. 处理好各种边界情况
4. 注意前导零的处理

掌握这道题的解法对理解单调栈的应用很有帮助。