leetcode
leetcode 1651 ~ 1700
插入后的最大值

插入后的最大值

难度:

标签:

题目描述

代码结果

运行时间: 51 ms, 内存: 16.7 MB


/*
 * 思路:
 * 1. 使用Java Stream API实现类似的逻辑。
 * 2. 首先判断是正数还是负数,根据情况决定插入的位置。
 * 3. 使用Stream的操作处理字符串的拼接。
 */
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public String maxValue(String n, int x) {
        boolean isNegative = n.charAt(0) == '-';
        int len = n.length();
        int index = IntStream.range(isNegative ? 1 : 0, len)
            .filter(i -> (isNegative && n.charAt(i) - '0' > x) ||
                          (!isNegative && n.charAt(i) - '0' < x))
            .findFirst().orElse(len);
        
        return IntStream.range(0, len + 1)
            .mapToObj(i -> i == index ? String.valueOf(x) : (i < index ? String.valueOf(n.charAt(i)) : String.valueOf(n.charAt(i - 1))))
            .collect(Collectors.joining());
    }
}

解释

方法:

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

时间复杂度:

O(m)

空间复杂度:

O(m)

代码细节讲解

🦆
题解为什么选择在正数中找到第一个小于x的数字前插入,而在负数中找到第一个大于x的数字前插入?这样的处理方式如何确保数值最大化?
对于正数,将x插入到第一个小于它的数字前是为了尽可能保持x较大的值在更高位,这样数值会更大。例如,对于n=275,x=6,插入结果为6275,比其他可能的结果如2765或2756更大。对于负数,将x插入第一个大于它的数字前是为了使负数的绝对值尽可能小,从而整个数值尽可能大(即尽可能接近零)。例如,对于n=-234,x=5,插入结果为-2534,这比-2354或-2345更接近零。
🦆
对于正数n,如果x比n中所有数字都大,题解建议将x插入到末尾。这种做法是如何确保结果是最大的?
如果x比n中所有数字都大,将x插入到末尾能保证生成的数最大。因为x较大,放在末尾不会影响前面已经较大的数值序列,而且这样还能保持x的较大值有效性。例如,n=321和x=9,插入后成为3219,显然这是最大的可能数值。
🦆
在处理负数时,如果所有数字都小于x,题解同样推荐将x添加到末尾。请问这种情况下这样做是否总是最优?
在负数情况下,如果所有数字都小于x,将x添加到末尾不一定是最优。最优的插入点应该是在第一个比x小的数字之前,但如果所有数字都小于x,按题解的处理,x将会被添加到末尾,这在大多数情况下会让负数的绝对值更大,从而使数值更小(更远离零)。例如,n=-123和x=4,插入后成为-1234,这并非最接近零的值。理论上,应该寻找最小的插入位来最大化数值,但由于所有数字都小于x,添加到末尾变成默认的行为。
🦆
在负数的处理逻辑中,题解从索引1开始遍历,这里为什么跳过了索引0,即负号?
在负数的处理中跳过索引0是因为索引0处是负号('-'),不是一个数字。负号标明了数值的正负性,不参与数字的大小比较和插入逻辑。因此,遍历和比较数字应从索引1开始,即负数的首个数字开始。

相关问题