解题思路

核心问题：数组中有一些 -1 需要填充，但只能选用一对正整数 (x, y) 来填充所有缺失位置，目标是最小化相邻元素绝对差的最大值。

算法选择：采用二分答案。最大相邻差值越小，可行性越差，具有单调性。二分这个最小可能的最大差值 d，用 check(d) 判断能否用一对 (x, y) 填充所有 -1，使相邻差 ≤ d。

验证可行性 (check 函数)：

1. 计算下界：先统计所有已知相邻元素的绝对差最大值 base，这是答案的天然下界。
2. 处理 -1 连续段：将每个连续的 -1 段抽象为三元组 (L, R, len)：
   · L：段左侧的已知数字（若不存在则等于 R）
   · R：段右侧的已知数字（若不存在则等于 L）
   · len：该段中 -1 的个数
3. 候选数对：对于给定的 d，最优候选对为 (mn + d, mx - d)：
   · mn = 所有约束中的最小值
   · mx = 所有约束中的最大值
4. 逐个验证：对每个 -1 段检查：
   · 全部填 x 是否可行（段内相邻差 ≤ d，且与边界差 ≤ d）
   · 全部填 y 是否可行
   · 若 len ≥ 2，尝试用 x 和 y 分段填充（如 xxx...yyy），要求 |x-y| ≤ d
   · 以上均不可行则返回 false

C语言实现

```c
#include <stdbool.h>
#include <stdlib.h>
#include <limits.h>

// 比较函数，用于 qsort
int cmp_int(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

// 检查在最大差值为 d 的情况下是否可行
bool check(int* nums, int numsSize, int d, int* pairs, int pairCount, 
           int mn, int mx, int base) {
    if (d < base) return false;
    
    int x = mn + d;
    int y = mx - d;
    if (x > y) {
        int tmp = x; x = y; y = tmp;
    }
    
    for (int i = 0; i < pairCount; i++) {
        int L = pairs[i * 3];
        int R = pairs[i * 3 + 1];
        int len = pairs[i * 3 + 2];
        
        // 尝试全部填 x
        bool okX = true;
        if (abs(x - L) > d || abs(x - R) > d) okX = false;
        if (len >= 2 && abs(x - x) > d) okX = false; // 恒成立，占位
        // 段内相邻差：全部填 x，差为 0
        if (okX) continue;
        
        // 尝试全部填 y
        bool okY = true;
        if (abs(y - L) > d || abs(y - R) > d) okY = false;
        if (okY) continue;
        
        // 尝试分段填充（x 和 y 混合），需要 len >= 2
        if (len >= 2 && abs(x - y) <= d) {
            // 检查边界：靠近 L 的一侧填 x，靠近 R 的一侧填 y
            bool okSplit = true;
            if (abs(x - L) > d || abs(y - R) > d) okSplit = false;
            // 段内 x 和 y 交界处差为 |x-y|，已检查 <= d
            if (okSplit) continue;
            
            // 交换 x 和 y 的位置再试一次
            okSplit = true;
            if (abs(y - L) > d || abs(x - R) > d) okSplit = false;
            if (okSplit) continue;
        }
        
        return false;
    }
    return true;
}

int minDifference(int* nums, int numsSize) {
    // 1. 计算 base：已知相邻元素的最大绝对差
    int base = 0;
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] != -1 && nums[i + 1] != -1) {
            int diff = abs(nums[i] - nums[i + 1]);
            if (diff > base) base = diff;
        }
    }
    
    // 2. 提取所有 -1 连续段
    int pairs[100000 * 3]; // 最多 numsSize/2 段
    int pairCount = 0;
    int mn = INT_MAX, mx = INT_MIN;
    
    int i = 0;
    while (i < numsSize) {
        if (nums[i] != -1) {
            i++;
            continue;
        }
        int start = i;
        while (i < numsSize && nums[i] == -1) i++;
        int end = i - 1;
        int len = end - start + 1;
        
        int L = (start > 0) ? nums[start - 1] : -1;
        int R = (end < numsSize - 1) ? nums[end + 1] : -1;
        
        // 处理边界：若一侧无边界，用另一侧的值代替
        if (L == -1 && R == -1) {
            // 全是 -1，答案为 0
            return 0;
        }
        if (L == -1) L = R;
        if (R == -1) R = L;
        
        pairs[pairCount * 3] = (L < R) ? L : R;
        pairs[pairCount * 3 + 1] = (L < R) ? R : L;
        pairs[pairCount * 3 + 2] = len;
        pairCount++;
        
        if (L < mn) mn = L;
        if (R < mn) mn = R;
        if (L > mx) mx = L;
        if (R > mx) mx = R;
    }
    
    // 3. 如果没有 -1，直接返回 base
    if (pairCount == 0) return base;
    
    // 4. 二分答案
    int left = base;
    int right = mx - mn; // 最大可能差值
    if (right < left) right = left;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(nums, numsSize, mid, pairs, pairCount, mn, mx, base)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
```

复杂度分析

· 时间复杂度：O(n log V)，其中 n 为数组长度，V 为值域范围（≤ 10⁹）。每次二分需 O(n) 扫描验证。
· 空间复杂度：O(n)，用于存储所有 -1 连续段的信息。