Medium

题目描述

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

解题思路

这是一个经典的贪心算法问题，核心思想是要让高位的数字尽可能小。

基本思路：

  1. 使用单调栈维护一个递增序列
  2. 遍历数字字符串，对于当前数字，如果它比栈顶元素小且还有删除次数，就删除栈顶元素
  3. 这样可以保证高位数字尽可能小

具体步骤：

  1. 初始化一个栈（或数组）来存储结果
  2. 遍历每个数字字符：
    • 当栈不为空、当前字符小于栈顶、且还能删除时，弹出栈顶元素
    • 将当前字符入栈
  3. 如果删除次数还没用完，从末尾继续删除
  4. 处理前导零和空结果的情况

这种方法的核心在于贪心策略：总是优先删除会让高位变大的数字，从而保证结果最小。

时间复杂度为O(n)，每个字符最多入栈和出栈一次；空间复杂度为O(n)，用于存储结果。

代码实现

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<char> stack;
        int toRemove = k;
        
        for (char digit : num) {
            while (!stack.empty() && stack.back() > digit && toRemove > 0) {
                stack.pop_back();
                toRemove--;
            }
            stack.push_back(digit);
        }
        
        // Remove remaining digits from the end
        while (toRemove > 0) {
            stack.pop_back();
            toRemove--;
        }
        
        // Build result and remove leading zeros
        string result = "";
        for (char digit : stack) {
            if (!(result.empty() && digit == '0')) {
                result += digit;
            }
        }
        
        return result.empty() ? "0" : result;
    }
};

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        to_remove = k
        
        for digit in num:
            while stack and stack[-1] > digit and to_remove > 0:
                stack.pop()
                to_remove -= 1
            stack.append(digit)
        
        # Remove remaining digits from the end
        while to_remove > 0:
            stack.pop()
            to_remove -= 1
        
        # Build result and remove leading zeros
        result = ''.join(stack).lstrip('0')
        
        return result if result else '0'

public class Solution {
    public string RemoveKdigits(string num, int k) {
        var stack = new List<char>();
        int toRemove = k;
        
        foreach (char digit in num) {
            while (stack.Count > 0 && stack[stack.Count - 1] > digit && toRemove > 0) {
                stack.RemoveAt(stack.Count - 1);
                toRemove--;
            }
            stack.Add(digit);
        }
        
        // Remove remaining digits from the end
        while (toRemove > 0) {
            stack.RemoveAt(stack.Count - 1);
            toRemove--;
        }
        
        // Build result and remove leading zeros
        var result = new System.Text.StringBuilder();
        foreach (char digit in stack) {
            if (!(result.Length == 0 && digit == '0')) {
                result.Append(digit);
            }
        }
        
        return result.Length == 0 ? "0" : result.ToString();
    }
}

var removeKdigits = function(num, k) {
    const stack = [];
    let toRemove = k;
    
    for (let digit of num) {
        while (stack.length > 0 && stack[stack.length - 1] > digit && toRemove > 0) {
            stack.pop();
            toRemove--;
        }
        stack.push(digit);
    }
    
    // Remove remaining digits from the end
    while (toRemove > 0) {
        stack.pop();
        toRemove--;
    }
    
    // Build result and remove leading zeros
    let result = stack.join('').replace(/^0+/, '');
    
    return result || '0';
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个字符最多入栈和出栈一次
空间复杂度O(n)栈最多存储n个字符

相关题目