1946-子字符串突变后可能得到的最大整数

给你一个字符串 num ，该字符串表示一个大整数。另给你一个长度为 10 且 下标从 0 开始 的整数数组 change ，该数组将
0-9 中的每个数字映射到另一个数字。更规范的说法是，数字 d 映射为数字 change[d] 。

你可以选择突变 num 的任一子字符串。突变子字符串意味着将每位数字 num[i] 替换为该数字在 change
中的映射（也就是说，将 num[i] 替换为 change[num[i]]）。

请你找出在对 num 的任一子字符串执行突变操作（也可以不执行）后，可能得到的 最大整数 ，并用字符串表示返回。

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

示例 1：

**输入：** num = " ** _1_** 32", change = [9,8,5,0,3,6,4,2,6,8]
**输出：** " ** _8_** 32"
**解释：** 替换子字符串 "1"：
- 1 映射为 change[1] = 8 。
因此 " ** _1_** 32" 变为 " ** _8_** 32" 。
"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 <= 105
num 仅由数字 0-9 组成
change.length == 10
0 <= change[d] <= 9

方法一：贪心

提示 1

为了使得子串突变后的数值最大，我们需要尽可能寻找突变后数值会增大的较高的位，并将该位作为突变子串的左边界。

提示 1 解释

首先假设对于任意数位，突变前后数值一定会发生改变。那么考虑任意两个数位，较高的位突变所产生的改变量绝对值一定大于较低的位突变产生的改变量绝对值。因此，在这种情况下，为了使得子串突变后数值最大，我们需要将突变后数值会增大的最高数位作为突变子串的左边界。

下面考虑存在某些数位突变前后数值不变的情况。显然，我们只需要考虑该位比之前得到的数位更高的情况，此时仅突变前者的改变量为 0，而仅突变后者的改变量大于 0。同时考虑到这两个数位之间可能存在突变后数值会减小的数位，因此前者作为左边界的最大改变量一定不会大于后者作为左边界的最大改变量，我们仍然需要将后者作为突变子串的左边界。

提示 2

确定了突变子串的左边界（如果存在）后，如果当前右边界的右侧相邻数位满足突变后数值不减小，则我们应当延伸右边界。

提示 2 解释

考虑当前右边界的右侧相邻数位。此时会有三种情况：

如果该数位突变后数值减小，那么无论在当前的基础上如何延伸右边界，延伸后整数的突变后数值一定小于延伸前的对应数值。
如果该数位突变后增大，那么我们显然应当延伸右边界。
如果该数位突变后不变，那么延伸右边界前后整数的突变后数值不会改变。但该数位右侧可能存在突变后数值增大的数位，因此我们应当延伸右边界。

思路与算法

我们从高位到低位（从左向右）遍历 num，并根据 提示 1 寻找第一个突变后数值会增大的数位作为突变子串的左边界。如果不存在，突变子串位空字符串，亦即不执行突变。

在确定左边界后，此时右边界初始与左边界重合，我们根据 提示 2 尝试延伸突变子串的右边界。如果当前右边界右侧的数位满足突变后数值大于等于突变前数值，则我门将右边界延伸一位。

我们可以在确定左边界与延伸右边界时对字符串进行修改，并在确定完成左右边界后返回该字符串作为答案。

代码

[sol1-C++]class Solution {
public:
    string maximumNumber(string num, vector<int>& change) {
        int n = num.size();
        for (int i = 0; i < n; ++i){
            // 寻找第一个突变后数值更大的位作为左边界
            if (change[num[i]-'0'] > num[i] - '0'){
                // 尝试更新右边界
                while (i < n && change[num[i]-'0'] >= num[i] - '0'){
                    num[i] = '0' + change[num[i]-'0'];
                    ++i;
                }
                break;
            }
        }
        return num;
    }
};

[sol1-Python3]class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        n = len(num)
        num = list(num)
        for i in range(n):
            # 寻找第一个突变后数值更大的位作为左边界
            if change[int(num[i])] > int(num[i]):
                # 尝试更新右边界
                while i < n and change[int(num[i])] >= int(num[i]):
                    num[i] = str(change[int(num[i])])
                    i += 1
                break
        return ''.join(num)

复杂度分析

时间复杂度：O(n)，其中 n 为 num 的长度。即为一次遍历同时更新 num 的时间复杂度。
空间复杂度：由于不同语言的字符串实现与方法不同，空间复杂度也有所不同。对于 C++ 解法，空间复杂度为 O(1)；而对于 Python 解法，空间复杂度为 O(n)。