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

福大大架构师每日一题

发布于 2025-12-18 10:24:10

2090

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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)
            }
        } elseif i > 0 {
            updateAns(v, v, false)
        }
        preI = i
    }
    if0 <= 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 >= 0else -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

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

    return ans


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