Medium

题目描述

给你一个字符串 num，表示一个大整数。另给你一个长度为 10 的整数数组 change，该数组将每个数字 0-9 映射到另一个数字。更正式地说，数字 d 映射到数字 change[d]。

你可以选择 变更 num 的一个子字符串。要变更子字符串，将子字符串中的每个数字 num[i] 替换为它在 change 中映射的数字（即，将 num[i] 替换为 change[num[i]]）。

返回一个字符串，表示变更（或不变更）一个子字符串后能得到的最大整数。

子字符串 是字符串中的一个连续字符序列。

示例 1:

输入: num = "132", change = [9,8,5,0,3,6,4,2,6,8]
输出: "832"
解释: 替换子字符串 "1":
- 1 映射到 change[1] = 8
因此，"132" 变为 "832"。
"832" 是能创建的最大数字，所以返回它。

示例 2:

输入: num = "021", change = [9,4,3,5,7,2,1,9,0,6]
输出: "934"
解释: 替换子字符串 "021":
- 0 映射到 change[0] = 9
- 2 映射到 change[2] = 3
- 1 映射到 change[1] = 4
因此，"021" 变为 "934"。
"934" 是能创建的最大数字，所以返回它。

示例 3:

输入: num = "5", change = [1,4,7,5,3,2,5,6,9,4]
输出: "5"
解释: "5" 已经是能创建的最大数字，所以返回它。

约束条件:

  • 1 <= num.length <= 10^5
  • num 只由数字 0-9 组成
  • change.length == 10
  • 0 <= change[d] <= 9

解题思路

这道题需要使用贪心策略来解决。核心思路是找到一个连续的子字符串进行变更，使得整个数字最大。

贪心策略分析：

  1. 从左到右扫描：为了使数字最大，我们应该尽可能让高位变大，所以从左到右扫描数字
  2. 开始变更的条件：当遇到第一个能够变得更大的数字时（即 change[digit] > digit），开始变更
  3. 停止变更的条件：一旦开始变更，就要连续变更直到遇到会变小的数字（即 change[digit] < digit）为止

算法步骤：

  1. 遍历字符串，寻找第一个能变大的数字位置
  2. 从该位置开始连续变更，直到遇到会变小的数字或字符串结束
  3. 如果某个数字变更后不变（change[digit] == digit），继续变更以保持子字符串的连续性

这种贪心策略是最优的，因为：

  • 越靠前的位置对数字大小影响越大
  • 一旦开始变更就要保持连续性，不能跳过中间的数字

代码实现

class Solution {
public:
    string maximumNumber(string num, vector<int>& change) {
        int n = num.length();
        bool started = false;
        
        for (int i = 0; i < n; i++) {
            int digit = num[i] - '0';
            int newDigit = change[digit];
            
            if (!started) {
                if (newDigit > digit) {
                    num[i] = '0' + newDigit;
                    started = true;
                }
            } else {
                if (newDigit < digit) {
                    break;
                }
                num[i] = '0' + newDigit;
            }
        }
        
        return num;
    }
};

class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        num = list(num)
        n = len(num)
        started = False
        
        for i in range(n):
            digit = int(num[i])
            new_digit = change[digit]
            
            if not started:
                if new_digit > digit:
                    num[i] = str(new_digit)
                    started = True
            else:
                if new_digit < digit:
                    break
                num[i] = str(new_digit)
        
        return ''.join(num)

public class Solution {
    public string MaximumNumber(string num, int[] change) {
        char[] arr = num.ToCharArray();
        int n = arr.Length;
        bool started = false;
        
        for (int i = 0; i < n; i++) {
            int digit = arr[i] - '0';
            int newDigit = change[digit];
            
            if (!started) {
                if (newDigit > digit) {
                    arr[i] = (char)('0' + newDigit);
                    started = true;
                }
            } else {
                if (newDigit < digit) {
                    break;
                }
                arr[i] = (char)('0' + newDigit);
            }
        }
        
        return new string(arr);
    }
}

var maximumNumber = function(num, change) {
    let arr = num.split('');
    let n = arr.length;
    let started = false;
    
    for (let i = 0; i < n; i++) {
        let digit = parseInt(arr[i]);
        let newDigit = change[digit];
        
        if (!started) {
            if (newDigit > digit) {
                arr[i] = newDigit.toString();
                started = true;
            }
        } else {
            if (newDigit < digit) {
                break;
            }
            arr[i] = newDigit.toString();
        }
    }
    
    return arr.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历整个字符串一次，n为字符串长度
空间复杂度O(1) 或 O(n)C++直接修改原字符串为O(1)，其他语言需要额外空间存储结果为O(n)