Easy

题目描述

给你一个表示正整数的字符串 number 和一个字符 digit。

从 number 中恰好移除 一次 digit 字符，返回移除后的结果字符串，使得剩余数字的十进制值最大。题目数据保证 digit 在 number 中至少出现一次。

示例 1：

输入：number = "123", digit = "3"
输出："12"
解释："123" 中只有一个 '3'。移除 '3' 后，结果是 "12"。

示例 2：

输入：number = "1231", digit = "1"
输出："231"
解释：我们可以移除第一个 '1' 得到 "231"，或者移除第二个 '1' 得到 "123"。
由于 231 > 123，我们返回 "231"。

示例 3：

输入：number = "551", digit = "5"
输出："51"
解释：我们可以从 "551" 中移除第一个或第二个 '5'。
两种情况都会得到字符串 "51"。

提示：

  • 2 <= number.length <= 100
  • number 由数字 '1' 到 '9' 组成
  • digit 是数字 '1' 到 '9' 中的一个
  • digit 在 number 中至少出现一次

解题思路

这道题要求移除指定数字的一次出现，使得结果数值最大。关键思路是：为了让数字最大，我们应该尽早移除会让数字变小的位置。

具体分析有两种方法：

方法一：贪心策略（推荐） 从左到右遍历字符串，当遇到目标数字时：

  • 如果这个数字的下一位比它大，就移除当前位置的数字
  • 如果遍历完都没找到这样的位置，就移除最后一次出现的目标数字

这个策略基于贪心思想：越早移除较小的数字，对结果的正面影响越大。

方法二：枚举所有可能 遍历所有目标数字出现的位置，移除每一个，然后比较得到的字符串大小，选择最大的。

由于字符串长度最大100，方法二的复杂度也完全可接受，但方法一更优雅。

时间复杂度方面，方法一是O(n)，方法二是O(n²)（字符串比较需要O(n)）。

代码实现

class Solution {
public:
    string removeDigit(string number, char digit) {
        int n = number.length();
        
        // 贪心策略：找到第一个digit，且其后面的数字比它大
        for (int i = 0; i < n - 1; i++) {
            if (number[i] == digit && number[i + 1] > digit) {
                return number.substr(0, i) + number.substr(i + 1);
            }
        }
        
        // 如果没找到，移除最后一个digit
        for (int i = n - 1; i >= 0; i--) {
            if (number[i] == digit) {
                return number.substr(0, i) + number.substr(i + 1);
            }
        }
        
        return "";
    }
};

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        n = len(number)
        
        # 贪心策略：找到第一个digit，且其后面的数字比它大
        for i in range(n - 1):
            if number[i] == digit and number[i + 1] > digit:
                return number[:i] + number[i + 1:]
        
        # 如果没找到，移除最后一个digit
        for i in range(n - 1, -1, -1):
            if number[i] == digit:
                return number[:i] + number[i + 1:]
        
        return ""

public class Solution {
    public string RemoveDigit(string number, char digit) {
        int n = number.Length;
        
        // 贪心策略：找到第一个digit，且其后面的数字比它大
        for (int i = 0; i < n - 1; i++) {
            if (number[i] == digit && number[i + 1] > digit) {
                return number.Substring(0, i) + number.Substring(i + 1);
            }
        }
        
        // 如果没找到，移除最后一个digit
        for (int i = n - 1; i >= 0; i--) {
            if (number[i] == digit) {
                return number.Substring(0, i) + number.Substring(i + 1);
            }
        }
        
        return "";
    }
}

var removeDigit = function(number, digit) {
    const n = number.length;
    
    // 贪心策略：找到第一个digit，且其后面的数字比它大
    for (let i = 0; i < n - 1; i++) {
        if (number[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型贪心方法枚举方法
时间复杂度O(n)O(n²)
空间复杂度O(1)O(n)

说明：

  • 贪心方法最多遍历字符串两次，时间复杂度为 O(n)
  • 枚举方法需要对每个可能位置生成新字符串并比较，时间复杂度为 O(n²)
  • 空间复杂度主要取决于字符串操作的临时空间开销

相关题目