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 = 0
            pre = -1
            for num in nums:
                if num != -1:
                    if num != pre:
                        ans.append(num)
                        cnt = 0
                elif cnt < 2:
                    ans.append(num)
                    cnt += 1
                pre = num
            if 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 ans
        
        nums = filter_nums(nums)
        if len(nums) == 1:
            return 0

        n = 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 False
                    if i+1 < n and nums[i+1] != -1 and abs(x - nums[i+1]) > k:
                        return False
                if x == -1:
                    _min, _max = 1, math.inf
                    if 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 False
                    ranges.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, r
                    if len(candidates) >= 2:
                        return False
                else:
                    _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):
                    continue
                elif len(candidates) == 2 and candidates[0][1] <= x+k and candidates[1][0] >= y-k and candidates[1][0] - candidates[0][1] <= k:
                    continue
                else:
                    return False
            return True
                        
        
        if is_possible(0):
            return 0
        
        i, j = 0, max(nums) - min(nums)
        while j - i > 1:
            m = (i+j) // 2
            if is_possible(m):
                j = m
            else:
                i = m
        return j