Medium

题目描述

给你一个非常大的整数 n，用字符串表示，以及一个整数数字 x。n 中的数字和数字 x 都在包含范围 [1, 9] 内，n 可能表示一个负数。

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

  • 例如，如果 n = 73 且 x = 6，最好将其插入到 7 和 3 之间，使 n = 763。
  • 如果 n = -55 且 x = 2，最好将其插入到第一个 5 之前，使 n = -255。

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

示例 1：

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

示例 2：

输入：n = "-13", x = 2
输出："-123"
解释：你可以让 n 变为 {-213, -123, -132} 中的一个，其中最大的是 -123。

约束：

  • 1 <= n.length <= 10^5
  • 1 <= x <= 9
  • n 中的数字在范围 [1, 9] 内
  • n 是整数的有效表示
  • 对于负数 n，它将以 ‘-’ 开头

解题思路

这是一个贪心算法问题，关键在于理解正数和负数的处理策略。

核心思路：

  1. 正数情况：要使结果最大，应该找到第一个比 x 小的数字，在其前面插入 x。这样可以让更大的数字出现在更高的位数上。

    • 遍历字符串，找到第一个 n[i] < x 的位置插入
    • 如果没有找到，说明所有数字都 ≥ x，则在末尾插入

  2. 负数情况：要使结果最大（绝对值最小），应该找到第一个比 x 大的数字，在其前面插入 x。这样可以让绝对值尽可能小。

    • 跳过负号，从第二个字符开始遍历
    • 找到第一个 n[i] > x 的位置插入
    • 如果没有找到，说明所有数字都 ≤ x，则在末尾插入

算法步骤：

  1. 判断是否为负数
  2. 根据正负数采用不同的比较策略
  3. 找到合适的插入位置
  4. 构造结果字符串

时间复杂度为 O(n)，空间复杂度为 O(n)（用于存储结果）。

代码实现

class Solution {
public:
    string maxValue(string n, int x) {
        char xChar = '0' + x;
        bool isNegative = n[0] == '-';
        int pos = -1;
        
        for (int i = isNegative ? 1 : 0; i < n.length(); i++) {
            if ((!isNegative && n[i] < xChar) || (isNegative && n[i] > xChar)) {
                pos = i;
                break;
            }
        }
        
        if (pos == -1) {
            return n + xChar;
        } else {
            return n.substr(0, pos) + xChar + n.substr(pos);
        }
    }
};

class Solution:
    def maxValue(self, n: str, x: int) -> str:
        x_char = str(x)
        is_negative = n[0] == '-'
        pos = -1
        
        start = 1 if is_negative else 0
        for i in range(start, len(n)):
            if (not is_negative and n[i] < x_char) or (is_negative and n[i] > x_char):
                pos = i
                break
        
        if pos == -1:
            return n + x_char
        else:
            return n[:pos] + x_char + n[pos:]

public class Solution {
    public string MaxValue(string n, int x) {
        char xChar = (char)('0' + x);
        bool isNegative = n[0] == '-';
        int pos = -1;
        
        for (int i = isNegative ? 1 : 0; i < n.Length; i++) {
            if ((!isNegative && n[i] < xChar) || (isNegative && n[i] > xChar)) {
                pos = i;
                break;
            }
        }
        
        if (pos == -1) {
            return n + xChar;
        } else {
            return n.Substring(0, pos) + xChar + n.Substring(pos);
        }
    }
}

var maxValue = function(n, x) {
    const xChar = x.toString();
    const isNegative = n[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次找到插入位置
空间复杂度O(n)需要存储结果字符串