What is the main pattern in Maximum Value after Insertion?

It is a greedy string scan with an invariant about the earliest digit that improves the final value. For positive numbers, insert before the first digit smaller than x. For negative numbers, insert before the first digit larger than x because a smaller magnitude means a larger signed value.

Why is the first valid position always optimal?

Because earlier digits have more weight than later digits. Once you find a position where placing x improves the prefix, any later insertion keeps a worse prefix and cannot recover that loss with later digits.

Why does the negative case use the opposite comparison?

A negative number is larger when its absolute value is smaller. After the minus sign, you want the digit sequence to become smaller as early as possible, so you place x before the first digit that is greater than x.

Do equal digits matter in the insertion rule?

Yes. If the current digit equals x, inserting before it does not improve the prefix, so you keep scanning. That is why n = 99 and x = 9 can return 999 no matter where 9 is inserted.

Can I solve Maximum Value after Insertion by brute force?

You could generate every insertion and compare results, but that costs too much for long strings and hides the real interview insight. The intended solution is the one-pass greedy rule based on the sign and the first improving position.

#1881

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

插入后的最大值

给你一个非常大的整数 n 和一个整数数字 x ，大整数 n 用一个字符串表示。 n 中每一位数字和数字 x 都处于闭区间 [1, 9] 中，且 n 可能表示一个负数。你打算通过在 n 的十进制表示的任意位置插入 x 来最大化 n 的数值。但不能在负号的左边插入 x 。例…

字符串贪心

题目描述

给你一个非常大的整数 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 <= 10⁵
1 <= x <= 9
n 中每一位的数字都在闭区间 [1, 9] 中。
n 代表一个有效的整数。
当 n 表示负数时，将会以字符 '-' 开始。

lightbulb

解题思路

方法一：贪心

如果 $n$ 是负数，那么我们要找到第一个大于 $x$ 的位置，然后在这个位置插入 $x$ ；如果 $n$ 是正数，那么我们要找到第一个小于 $x$ 的位置，然后在这个位置插入 $x$ 。

时间复杂度 $O(m)$ ，其中 $m$ 为 $n$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxValue(self, n: str, x: int) -> str:
        i = 0
        if n[0] == "-":
            i += 1
            while i < len(n) and int(n[i]) <= x:
                i += 1
        else:
            while i < len(n) and int(n[i]) >= x:
                i += 1
        return n[:i] + str(x) + n[i:]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They mention that n is stored as a string because numeric conversion is unsafe at this size.
question_mark
They hint that the negative case is the same scan shape but with the opposite comparison rule.
question_mark
They care about the first valid insertion point, which is the greedy invariant that makes later positions suboptimal.

warning

常见陷阱

外企场景

error
Using the positive-number rule on negative input and inserting before a smaller digit instead of a larger one.
error
Trying every insertion position and comparing full candidate strings, which is unnecessary and too slow for n.length up to 10^5.
error
Converting n into an integer type, which can overflow and also ignores that this is a string-order greedy problem.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the minimum value after insertion instead of the maximum, which flips the comparison rule for both signs.
arrow_right_alt
Insert a digit into a non-negative decimal string with leading-zero rules, where the insertion condition must respect formatting constraints.
arrow_right_alt
Insert multiple digits from a second string, where the single-step greedy rule becomes a merge-style decision process.

help

常见问题

外企场景

继续练习

#1864 构成交替字符串需要的最小交换次数 #1903 字符串中的最大奇数 #1850 邻位交换的最小次数