题目描述

给你一个整数数组 nums。nums 中的一些值 缺失 了，缺失的元素标记为 -1。

你需要选择 一个正 整数数对 (x, y)，并将 nums 中每一个 缺失 元素用 x 或者 y 替换。

你的任务是替换 nums 中的所有缺失元素，最小化 替换后数组中相邻元素 绝对差值 的 最大值。

请你返回上述要求下的 最小值。

样例

输入：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

输入：nums = [-1,-1,-1]

输出：0

解释：

选择数对 (4, 4)，nums 变为 [4, 4, 4]。

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

输出：1

解释：

选择数对 (11, 9) ，nums 变为 [11, 10, 9, 8]。

限制

• 2 <= nums.length <= 10^5
• nums[i] 要么是 -1，要么是范围 [1, 10^9] 中的一个整数。

算法

(二分答案，贪心，动态规划) $O(n \log U)$

1. 假设现在给定了 $x$ 和 $y$，则可以通过动态规划求出填充 $-1$ 的最小差值。动态规划的思路如下：
   1. 设状态 $f(i)$ 表示当前在 $i$ 位置，且上一个 $-1$ 位置填充了 $x$ 的最大差值，$g(i)$ 表示 上一个 $-1$ 位置 填充了 $y$ 的最大差值。
   2. 初始时，$f(0) = g(0) = 0$，其余待定。
   3. 转移时，如果 $nums(i) == -1$，则 $f(i) = \min(\max(f(i - 1), |x - px|), \max(g(i - 1), |x - py|))$，$f(i) = \min(\max(f(i - 1), |y - px|), \max(g(i - 1), |y - py|))$。否则，$f(i) = \max(f(i - 1), |nums(i) - px|)$，$g(i) = \max(g(i - 1), |nums(i) - py|)$。其中 $px$ 和 $py$ 是 上一个位置 填充的值。
   4. 最终答案为 $\min(f(n - 1), g(n - 1))$。
2. 接下来需要尝试固定 $x$ 和 $y$。显然最终的最大差值是单调的，所以可以通过二分答案并进行判定。
3. 假设限制最大差值为 $k$，则 $x$ 可以设置为与 $-1$ 相邻数字中的最小值 $mi$ 加 $k$，$y$ 可以设置为与 $-1$ 相邻数字中的最大值 $ma$ 减 $k$。
4. 二分的下界为相邻非 $-1$ 数字的最大差值，上界为 $\lfloor \frac{ma - mi}{2} \rfloor$。

时间复杂度

• 判定动态规划的状态数为 $O(n)$，转移时间为常数，故单次判定的时间复杂度为 $O(n)$。
• 二分的上下界为 $O(U)$，其中 $U$ 是最大的正整数。
• 故总时间复杂度为 $O(n \log U)$。

空间复杂度

• 动态规划的每一个状态仅与上一个状态相关，故可以使用一个变量表示状态。
• 优化空间后，仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minDifference(vector<int>& nums) {
        const int n = nums.size();

        int mi = INT_MAX, ma = 0, d = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] != -1 && nums[i - 1] != -1)
                d = max(d, abs(nums[i] - nums[i - 1]));

            if (
                nums[i] != -1 && 
                (
                    (i > 0 && nums[i - 1] == -1) || 
                    (i < n - 1 && nums[i + 1] == -1)
                )
            ) {
                mi = min(mi, nums[i]);
                ma = max(ma, nums[i]);
            }
        }

        if (mi == INT_MAX)
            return d;

        auto check = [&](int k) {
            int x = mi + k, y = ma - k;

            int f = 0, g = 0;
            int px = x, py = y;
            if (nums[0] != -1)
                px = py = nums[0];

            for (int i = 1; i < n; i++) {
                if (nums[i] == -1) {
                    int tf = f, tg = g;
                    f = min(
                            max(tf, abs(x - px)), 
                            max(tg, abs(x - py))
                        );
                    g = min(
                            max(tf, abs(y - px)),
                            max(tg, abs(y - py))
                        );
                    px = x; py = y;
                } else {
                    f = max(f, abs(nums[i] - px));
                    g = max(g, abs(nums[i] - py));
                    px = py = nums[i];
                }

                if (min(f, g) > k)
                    return false;
            }

            return true;
        };

        int l = d, r = (ma - mi + 1) / 2;
        while (l < r) {
            int mid = (l + r) >> 1;

            if (check(mid)) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};