插入后的最大值

标签: 贪心 字符串

难度: Medium

给你一个非常大的整数 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 的最大值。

 

示例 1：

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

示例 2：

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

 

提示：

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

Submission

运行时间: 51 ms

内存: 16.7 MB

class Solution:
    def maxValue(self, n: str, x: int) -> str:
        x = str(x)
        m = len(n)
        if n[0] == '-':
            for i in range(1, m):
                if n[i] > x:
                    return '-' + n[1:i] + x + n[i:]
        else:
            for i in range(m):
                if n[i] < x:
                    return n[:i] + x + n[i:]
        return n + x

Explain

题解的核心思路是根据整数n的正负性来决定x的插入位置。如果n是正数，为了使得n的数值最大，x应该被插入到n中第一个比x小的数字之前；如果n是负数，则x应该被插入到n中第一个比x大的数字之前。这样可以确保在保持数字正负性的前提下，n的绝对值尽可能大。特别地，如果遍历完n都没有找到合适的插入位置，则直接将x插入到n的末尾。

时间复杂度: O(m)

空间复杂度: O(m)

class Solution:
    def maxValue(self, n: str, x: int) -> str:
        x = str(x)  # 将整数x转换为字符串
        m = len(n)  # 获取n的长度
        if n[0] == '-':  # 如果n是负数
            for i in range(1, m):  # 从第1个位置开始遍历n
                if n[i] > x:  # 找到第一个大于x的数字
                    return '-' + n[1:i] + x + n[i:]  # 在该位置前插入x
        else:  # 如果n是正数
            for i in range(m):  # 遍历n的每一个位置
                if n[i] < x:  # 找到第一个小于x的数字
                    return n[:i] + x + n[i:]  # 在该位置前插入x
        return n + x  # 如果没有合适的插入位置，将x添加到末尾

Explore

对于正数，将x插入到第一个小于它的数字前是为了尽可能保持x较大的值在更高位，这样数值会更大。例如，对于n=275，x=6，插入结果为6275，比其他可能的结果如2765或2756更大。对于负数，将x插入第一个大于它的数字前是为了使负数的绝对值尽可能小，从而整个数值尽可能大（即尽可能接近零）。例如，对于n=-234，x=5，插入结果为-2534，这比-2354或-2345更接近零。

如果x比n中所有数字都大，将x插入到末尾能保证生成的数最大。因为x较大，放在末尾不会影响前面已经较大的数值序列，而且这样还能保持x的较大值有效性。例如，n=321和x=9，插入后成为3219，显然这是最大的可能数值。

在负数情况下，如果所有数字都小于x，将x添加到末尾不一定是最优。最优的插入点应该是在第一个比x小的数字之前，但如果所有数字都小于x，按题解的处理，x将会被添加到末尾，这在大多数情况下会让负数的绝对值更大，从而使数值更小（更远离零）。例如，n=-123和x=4，插入后成为-1234，这并非最接近零的值。理论上，应该寻找最小的插入位来最大化数值，但由于所有数字都小于x，添加到末尾变成默认的行为。

在负数的处理中跳过索引0是因为索引0处是负号（'-'），不是一个数字。负号标明了数值的正负性，不参与数字的大小比较和插入逻辑。因此，遍历和比较数字应从索引1开始，即负数的首个数字开始。