Leetcode 3357. Minimize the Maximum Adjacent Element Difference

Leetcode 3357. Minimize the Maximum Adjacent Element Difference
- 1. 解题思路
- 2. 代码实现

题目链接：3357. Minimize the Maximum Adjacent Element Difference

1. 解题思路

这一题思路上和题目3356相似，同样是一个二分查找的题目，我们定义一个is_possible()函数来判断对于一个给定的 $k$ ，是否存在一个构造使得相邻两数的绝对差均不大于 $k$ ，然后二分查找最小的满足条件的 $k$ 即可。

但是在此之前，我们可以对原始数组进行一下简化，显然，如果有连续多个-1的情况，由于可选的数只有两个，因此，我们保留至多两个即可，其他我们总可以通过取同一个数字令其满足条件。另外，对于头尾的情况，我们保留至多一个-1即可，同理，在原始数组当中相同的相邻元素也可以直接过滤掉，保留一个即可，如此一来，我们即可简化一下数组。

然后，我们就只需要考察一下这个is_possible()函数的实现即可。

有关这个问题，我的实现思路是考察在给定的 $k$ 下，每一个位置可以填充的值的范围，然后得到一系列的范围之后对其进行归并，看其是否可以归并到至多两个数值区间内。此时，我们只要在这之多两个数值区间内各取一个，即可满足所有空白位置的要求。

当然，这里存在一个特例，即 $A XXB$ 的情况，我们需要特殊考察一下，因为它有以下两种构造方式：

两数取值相同，此时就退化为了 $A XB$ 的情况，我们就只要考察 $\cap [l, r] \cap [B-k, B+k]$ 不为空即可，其中 $[l, r]$ 是我们归并得到的取值区间。
两数取值不同，即 $A X Y B$ 的情况，此时，我们不但各自需要 $X, Y$ 满足与 $A, B$ 各自的范围条件，且需要满足 $X, Y$ 之间的差值同样不超过 $k$ 。

上述两条件满足其一，构造即可实现。

最后，我们将其翻译为代码语言即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minDifference(self, nums: List[int]) -> int:def filter_nums(nums):ans = []cnt = 0pre = -1for num in nums:if num != -1:if num != pre:ans.append(num)cnt = 0elif cnt < 2:ans.append(num)cnt += 1pre = numif len(ans) >= 2 and ans[0] == -1 and ans[1] == -1:ans.pop(0)if len(ans) >= 2 and ans[-1] == -1 and ans[-2] == -1:ans.pop()return ansnums = filter_nums(nums)if len(nums) == 1:return 0n = len(nums)if Counter(nums)[-1] == 0:return max(abs(nums[i] - nums[i+1]) for i in range(n-1))def is_possible(k):ranges = []two_gap = []for i, x in enumerate(nums):if x != -1:if i-1 >= 0 and nums[i-1] != -1 and abs(x - nums[i-1]) > k:return Falseif i+1 < n and nums[i+1] != -1 and abs(x - nums[i+1]) > k:return Falseif x == -1:_min, _max = 1, math.infif i-1 >= 0 and nums[i-1] != -1:_min = max(_min, nums[i-1] - k)_max = min(_max, nums[i-1] + k)if i+1 < n and nums[i+1] != -1:_min = max(_min, nums[i+1] - k)_max = min(_max, nums[i+1] + k)if _min > _max:return Falseranges.append([_min, _max])if i-1 >= 0 and nums[i-1] == -1:two_gap.append(sorted([nums[i-2], nums[i+1]]))ranges = sorted(ranges)candidates = []_min, _max = ranges[0]for l, r in ranges:if l > _max:candidates.append([_min, _max])_min, _max = l, rif len(candidates) >= 2:return Falseelse:_min = max(_min, l)_max = min(_max, r)candidates.append([_min, _max])for x, y in two_gap:if any(y-k <= x+k and (x+k >= l or y-k <= r) for l, r in candidates):continueelif len(candidates) == 2 and candidates[0][1] <= x+k and candidates[1][0] >= y-k and candidates[1][0] - candidates[0][1] <= k:continueelse:return Falsereturn Trueif is_possible(0):return 0i, j = 0, max(nums) - min(nums)while j - i > 1:m = (i+j) // 2if is_possible(m):j = melse:i = mreturn j

提交代码评测得到：耗时4481ms，占用内存33.3MB。