题目描述

给你一个非常大的整数 n 和一个整数数字 x，大整数 n 用一个字符串表示。n 中每一位数字和数字 x 都处于闭区间 [1, 9] 中，且 n 可能表示一个 负数。

你打算通过在 n 的十进制表示的任意位置插入 x 来 最大化 n 的 数值。但 不能 在负号的左边插入 x。

例如，如果 n = 73 且 x = 6，那么最佳方案是将 6 插入 7 和 3 之间，使 n = 763。
如果 n = -55 且 x = 2，那么最佳方案是将 2 插在第一个 5 之前，使 n = -255。

返回插入操作后，用字符串表示的 n 的最大值。

样例

输入：n = "99", x = 9
输出："999"
解释：不管在哪里插入 9，结果都是相同的。

输入：n = "-13", x = 2
输出："-123"
解释：向 n 中插入 x 可以得到 -213、-123 或者 -132，三者中最大的是 -123。

限制

• 1 <= n.length <= 10^5
• 1 <= x <= 9
• n 中每一位的数字都在闭区间 [1, 9] 中。
• n 代表一个有效的整数。
• 当 n 表示负数时，将会以字符 '-' 开始。

算法

(贪心) $O(len)$

1. 对于正数，插入的位置应该是从高位到低位中，第一个出现严格比 x 小的位置前边。
2. 对于负数，插入的位置应该是从高位到低位中，第一个出现严格比 x 大的位置前边。
3. 根据以上贪心规则模拟就行。

时间复杂度

• 遍历数组一次，构造答案移动整体数组一次，故总时间复杂度为 $O(len)$。

空间复杂度

• 需要 $O(len)$ 的额外空间存储返回的答案。

C++ 代码

class Solution {
public:
    string maxValue(string n, int x) {
        const int len = n.size();

        int pos = len;
        if (n[0] != '-') {
            for (int i = 0; i < len; i++) {
                if (x > n[i] - '0') {
                    pos = i;
                    break;
                }
            }
        } else {
            for (int i = 1; i < len; i++) {
                if (x < n[i] - '0') {
                    pos = i;
                    break;
                }
            }
        }

        n.push_back(0);
        for (int i = len; i > pos; i--)
            n[i] = n[i - 1];

        n[pos] = x + '0';
        return n;
    }
};