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^5nums[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 n = nums.length;
// 找出所有连续的-1段及其左右边界
const segments = []; // [leftVal, rightVal, length]
for (let i = 0; i < n; i++) {
if (nums[i]
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n log(max_val)) |
| 空间复杂度 | O(n) |
其中 n 是数组长度，max_val 是数组中的最大值。二分搜索的范围是 [0, 2×10^9]，每次检查需要 O(n) 时间。