2025-06-09：最小化相邻元素的最大差值。用go语言，给定一个整数数组 nums，其中部分元素被标记为 -1，表示这些元素缺失。

你需要选取一对正整数 (x, y)，将数组中所有 -1 替换为这两个数字之一。

目标是使替换后数组中任意相邻元素之间绝对差的最大值最小化。

请你计算并返回这个最小的最大绝对差值。

2 <= nums.length <= 100000。

nums[i] 要么是 -1 ，要么是范围 [1, 1000000000] 中的一个整数。

输入：nums = [1,2,-1,10,8]。

输出：4。

解释：

选择数对 (6, 7) ，nums 变为 [1, 2, 6, 10, 8] 。

相邻元素的绝对差值分别为：
|1 - 2| == 1
|2 - 6| == 4
|6 - 10| == 4
|10 - 8| == 2

题目来自力扣3357。

解决步骤

1. 确定关键数字：

   • minL：所有与-1相邻的非-1数字中的最小值。
   • maxR：所有与-1相邻的非-1数字中的最大值。
   • 在示例中，与-1相邻的数字是2和10，因此minL=2，maxR=10。

2. 处理非-1的相邻元素：

   • 遍历数组，计算所有相邻非-1元素的绝对差，记录最大值。
   • 在示例中，|1-2|=1和|10-8|=2，当前最大差为2。

3. 处理-1的连续段：

   • 对于连续的-1段（即多个连续的-1），我们需要确定如何填充x和y以最小化最大差。
   • 如果两个非-1数字之间有连续的-1：
     • 如果连续-1段长度为1（即单个-1），填充的值需要在左右非-1数字之间插值。
     • 如果连续-1段长度大于1，填充的值需要满足一定的间隔。
   • 在示例中，-1位于2和10之间，且长度为1。填充的值需要介于2和10之间。

4. 计算填充值的可能范围：

   • 对于单个-1，填充的值需要在左右非-1数字之间。例如，2和10之间的中间值是6，最大差为max(|2-6|, |6-10|)=4。
   • 对于多个-1，填充的值需要满足更复杂的间隔约束。

5. 更新答案：

   • 对于每个-1段，计算其可能贡献的最大差，并更新全局最大差。
   • 在示例中，填充6和7（实际只需填充6）使得最大差为4。

6. 边界情况：

   • 如果数组以-1开头或结尾，需要单独处理。
   • 在示例中，没有以-1开头或结尾的情况。

时间复杂度

• 遍历数组一次以计算minL和maxR：O(n)。
• 遍历数组一次以计算相邻非-1元素的差和-1段的处理：O(n)。
• 总体时间复杂度：O(n)。

空间复杂度

• 仅使用常数额外空间（如minL、maxR、ans等变量）。
• 总体额外空间复杂度：O(1)。

总结

1. 确定与-1相邻的最小和最大值（minL和maxR）。
2. 计算非-1相邻元素的最大差。
3. 处理-1段，计算填充值可能的最大差。
4. 结合minL和maxR，确定全局最小的最大差。
5. 时间和空间复杂度均为线性。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func minDifference(nums []int) (ans int) {
	n := len(nums)
	// 和空位相邻的最小数字 minL 和最大数字 maxR
	minL, maxR := math.MaxInt, 0
	for i, v := range nums {
		if v != -1 && (i > 0 && nums[i-1] == -1 || i < n-1 && nums[i+1] == -1) {
			minL = min(minL, v)
			maxR = max(maxR, v)
		}
	}

	updateAns := func(l, r int, big bool) {
		d := (min(r-minL, maxR-l) + 1) / 2
		if big {
			d = min(d, (maxR-minL+2)/3) // d 不能超过上界
		}
		ans = max(ans, d)
	}

	preI := -1
	for i, v := range nums {
		if v == -1 {
			continue
		}
		if preI >= 0 {
			if i-preI == 1 {
				ans = max(ans, abs(v-nums[preI]))
			} else {
				updateAns(min(nums[preI], v), max(nums[preI], v), i-preI > 2)
			}
		} else if i > 0 {
			updateAns(v, v, false)
		}
		preI = i
	}
	if 0 <= preI && preI < n-1 {
		updateAns(nums[preI], nums[preI], false)
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	nums := []int{1, 2, -1, 10, 8}
	fmt.Println(minDifference(nums))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

import math
from typing import List

def min_difference(nums: List[int]) -> int:
    n = len(nums)
    minL, maxR = math.inf, 0

    def min_val(a, b):
        return a if a < b else b

    def max_val(a, b):
        return a if a > b else b

    def abs_val(x):
        return x if x >= 0 else -x

    # 找和空位相邻的最小数字minL和最大数字maxR
    for i, v in enumerate(nums):
        if v != -1 and ((i > 0 and nums[i-1] == -1) or (i < n - 1 and nums[i + 1] == -1)):
            minL = min_val(minL, v)
            maxR = max_val(maxR, v)

    ans = 0

    def updateAns(l, r, big):
        nonlocal ans
        d = (min_val(r - minL, maxR - l) + 1) // 2
        if big:
            d = min_val(d, (maxR - minL + 2) // 3)
        ans = max_val(ans, d)

    preI = -1
    for i, v in enumerate(nums):
        if v == -1:
            continue
        if preI >= 0:
            if i - preI == 1:
                ans = max_val(ans, abs_val(v - nums[preI]))
            else:
                updateAns(min_val(nums[preI], v), max_val(nums[preI], v), i - preI > 2)
        else:
            if i > 0:
                updateAns(v, v, False)
        preI = i

    if 0 <= preI < n - 1:
        updateAns(nums[preI], nums[preI], False)

    return ans


if __name__ == '__main__':
    nums = [1, 2, -1, 10, 8]
    print(min_difference(nums))