3357. 最小化相邻元素差值的最大值

Hard

题目描述

给你一个整数数组 nums。nums 中的一些值缺失，用 -1 表示。

你必须恰好选择一对正整数 (x, y) 一次，并用 x 或 y 替换每个缺失的元素。

你需要在替换后最小化 nums 相邻元素之间绝对差值的最大值。

返回可能的最小差值。

示例 1：

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

示例 2：

输入：nums = [-1,-1,-1]
输出：0
解释：
通过选择 (4, 4) 这对数字，nums 可以变为 [4, 4, 4]。

示例 3：

输入：nums = [-1,10,-1,8]
输出：1
解释：
通过选择 (11, 9) 这对数字，nums 可以变为 [11, 10, 9, 8]。

约束条件：

2 <= nums.length <= 10^5
nums[i] 要么是 -1，要么在范围 [1, 10^9] 内。

解题思路

这是一道典型的二分搜索 + 贪心的题目。

核心思路：

我们需要选择两个正整数 x 和 y 来替换所有的 -1，使得相邻元素差值的最大值最小
可以对答案进行二分搜索，对于每个候选答案 d，检查是否能找到合适的 x 和 y 使得最大相邻差值不超过 d

关键观察：

超过2个连续的-1可以忽略，因为中间的-1可以用任意合适的值填充
可以在数组开头和结尾添加正数，确保所有连续的-1都被正数包围
对于最优解，总是存在 0 < x ≤ y，且选择 x = min(a) + d 是最优的，其中 a 是相邻的正数

算法步骤：

预处理数组，提取所有需要考虑的连续-1段
二分搜索答案 d
对于每个 d，检查是否能找到合适的 x 和 y：
- 遍历所有-1段，根据相邻的正数值确定 x 和 y 的约束
- 使用贪心策略：x = left + d（left是左边界），然后检查 y 的可行性
返回满足条件的最小 d

代码实现

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();
        
        // 找出所有连续的-1段及其左右边界
        vector<tuple<int, int, int>> segments; // (left_val, right_val, length)
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == -1) {
                int left_val = (i > 0) ? nums[i-1] : nums[i+1];
                int j = i;
                while (j < n && nums[j] == -1) j++;
                int right_val = (j < n) ? nums[j] : nums[i-1];
                int length = j - i;
                segments.push_back({left_val, right_val, min(2, length)});
                i = j - 1;
            }
        }
        
        // 计算现有相邻元素的最大差值
        int max_existing = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] != -1 && nums[i+1] != -1) {
                max_existing = max(max_existing, abs(nums[i] - nums[i+1]));
            }
        }
        
        auto check = [&](int d) -> bool {
            int x = -1, y = -1;
            
            for (auto [left_val, right_val, length] : segments) {
                if (length == 1) {
                    // 单个-1，需要找到一个值使得与两边的差都不超过d
                    int min_val = max(left_val - d, right_val - d);
                    int max_val = min(left_val + d, right_val + d);
                    if (min_val > max_val) return false;
                    
                    if (x == -1) {
                        x = min_val;
                    } else if (x < min_val || x > max_val) {
                        if (y == -1) {
                            y = min_val;
                        } else if (y < min_val || y > max_val) {
                            return false;
                        }
                    }
                } else {
                    // 两个连续的-1，需要x和y
                    if (x == -1) x = left_val + d;
                    if (y == -1) y = right_val - d;
                    
                    if (abs(left_val - x) > d || abs(x - y) > d || abs(y - right_val) > d) {
                        return false;
                    }
                }
            }
            
            return true;
        };
        
        int left = max_existing, right = 2e9;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 找出所有连续的-1段及其左右边界
        segments = []  # (left_val, right_val, length)
        
        i = 0
        while i < n:
            if nums[i] == -1:
                left_val = nums[i-1] if i > 0 else nums[i+1]
                j = i
                while j < n and nums[j] == -1:
                    j += 1
                right_val = nums[j] if j < n else nums[i-1]
                length = j - i
                segments.append((left_val, right_val, min(2, length)))
                i = j
            else:
                i += 1
        
        # 计算现有相邻元素的最大差值
        max_existing = 0
        for i in range(n - 1):
            if nums[i] != -1 and nums[i+1] != -1:
                max_existing = max(max_existing, abs(nums[i] - nums[i+1]))
        
        def check(d):
            x, y = -1, -1
            
            for left_val, right_val, length in segments:
                if length == 1:
                    # 单个-1
                    min_val = max(left_val - d, right_val - d)
                    max_val = min(left_val + d, right_val + d)
                    if min_val > max_val:
                        return False
                    
                    if x == -1:
                        x = min_val
                    elif x < min_val or x > max_val:
                        if y == -1:
                            y = min_val
                        elif y < min_val or y > max_val:
                            return False
                else:
                    # 两个连续的-1
                    if x == -1:
                        x = left_val + d
                    if y == -1:
                        y = right_val - d
                    
                    if abs(left_val - x) > d or abs(x - y) > d or abs(y - right_val) > d:
                        return False
            
            return True
        
        left, right = max_existing, 2 * 10**9
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int MinDifference(int[] nums) {
        int n = nums.Length;
        
        // 找出所有连续的-1段及其左右边界
        var segments = new List<(int leftVal, int rightVal, int length)>();
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == -1) {
                int leftVal = (i > 0) ? nums[i-1] : nums[i+1];
                int j = i;
                while (j < n && nums[j] == -1) j++;
                int rightVal = (j < n) ? nums[j] : nums[i-1];
                int length = j - i;
                segments.Add((leftVal, rightVal, Math.Min(2, length)));
                i = j - 1;
            }
        }
        
        // 计算现有相邻元素的最大差值
        int maxExisting = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] != -1 && nums[i+1] != -1) {
                maxExisting = Math.Max(maxExisting, Math.Abs(nums[i] - nums[i+1]));
            }
        }
        
        bool Check(int d) {
            int x = -1, y = -1;
            
            foreach (var (leftVal, rightVal, length) in segments) {
                if (length == 1) {
                    // 单个-1
                    int minVal = Math.Max(leftVal - d, rightVal - d);
                    int maxVal = Math.Min(leftVal + d, rightVal + d);
                    if (minVal > maxVal) return false;
                    
                    if (x == -1) {
                        x = minVal;
                    } else if (x < minVal || x > maxVal) {
                        if (y == -1) {
                            y = minVal;
                        } else if (y < minVal || y > maxVal) {
                            return false;
                        }
                    }
                } else {
                    // 两个连续的-1
                    if (x == -1) x = leftVal + d;
                    if (y == -1) y = rightVal - d;
                    
                    if (Math.Abs(leftVal - x) > d || Math.Abs(x - y) > d || Math.Abs(y - rightVal) > d) {
                        return false;
                    }
                }
            }
            
            return true;
        }
        
        int left = maxExisting, right = 2000000000;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (Check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

var minDifference = function(nums) {
    const segments = [];
    let existingMaximum = 0;
    let minimumBoundary = Infinity;
    let maximumBoundary = -Infinity;

    for (let i = 0; i + 1 < nums.length; i++) {
        if (nums[i] !== -1 && nums[i + 1] !== -1) {
            existingMaximum = Math.max(existingMaximum, Math.abs(nums[i] - nums[i + 1]));
        }
    }

    for (let start = 0; start < nums.length; ) {
        if (nums[start] !== -1) {
            start++;
            continue;
        }

        let end = start;
        while (end + 1 < nums.length && nums[end + 1] === -1) end++;
        const left = start > 0 ? nums[start - 1] : null;
        const right = end + 1 < nums.length ? nums[end + 1] : null;
        if (left !== null) {
            minimumBoundary = Math.min(minimumBoundary, left);
            maximumBoundary = Math.max(maximumBoundary, left);
        }
        if (right !== null) {
            minimumBoundary = Math.min(minimumBoundary, right);
            maximumBoundary = Math.max(maximumBoundary, right);
        }
        segments.push([left, right, end - start + 1]);
        start = end + 1;
    }

    if (minimumBoundary === Infinity) return existingMaximum;

    const canAchieve = (difference) => {
        const candidates = [minimumBoundary + difference, Math.max(1, maximumBoundary - difference)];

        for (const [left, right, length] of segments) {
            if (left === null && right === null) continue;
            let possible = false;

            for (const first of candidates) {
                if (left !== null && Math.abs(left - first) > difference) continue;
                if (right === null) {
                    possible = true;
                    break;
                }

                for (const last of candidates) {
                    if (Math.abs(right - last) > difference) continue;
                    if (first === last || (length >= 2 && Math.abs(first - last) <= difference)) {
                        possible = true;
                        break;
                    }
                }
                if (possible) break;
            }

            if (!possible) return false;
        }
        return true;
    };

    let low = existingMaximum;
    let high = 1_000_000_000;
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (canAchieve(mid)) high = mid;
        else low = mid + 1;
    }
    return low;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大小
时间复杂度	O(n log(max_val))
空间复杂度	O(n)

其中 n 是数组长度，max_val 是数组中的最大值。二分搜索的范围是 [0, 2×10^9]，每次检查需要 O(n) 时间。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目