Leetcode 3357. Minimize the Maximum Adjacent Element Difference

devtools/2024/11/19 18:06:21/
  • Leetcode 3357. Minimize the Maximum Adjacent Element Difference
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:3357. Minimize the Maximum Adjacent Element Difference

1. 解题思路

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

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

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

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

当然,这里存在一个特例,即 A X X B AXXB AXXB的情况,我们需要特殊考察一下,因为它有以下两种构造方式:

  • 两数取值相同,此时就退化为了 A X B AXB AXB的情况,我们就只要考察 [ A − k , A + k ] ∩ [ l , r ] ∩ [ B − k , B + k ] [A-k, A+k] \cap [l, r] \cap [B-k, B+k] [Ak,A+k][l,r][Bk,B+k]不为空即可,其中 [ l , r ] [l, r] [l,r]是我们归并得到的取值区间。
  • 两数取值不同,即 A X Y B AXYB AXYB的情况,此时,我们不但各自需要 X , Y X, Y X,Y满足与 A , B A,B A,B各自的范围条件,且需要满足 X , Y X, Y X,Y之间的差值同样不超过 k k 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。


http://www.ppmy.cn/devtools/135256.html

相关文章

论文解析:基于区块链的计算能力共享系统

目录 论文解析:基于区块链的计算能力共享系统 2区top 核心内容: 核心创新点的原理与理论: 进化博弈论构建了计算服务部门之间计算力共享策略的动态模型。 采用深度强化学习(DRL)设计了节点选择算法,以最小化各部门的计算力成本 深度强化学习:深度学习的感知能力和…

Bugku CTF_Web——字符?正则?

Bugku CTF_Web——字符&#xff1f;正则&#xff1f; 进入靶场 <?php highlight_file(2.php); $keyflag{********************************}; $IM preg_match("/key.*key.{4,7}key:\/.\/(.*key)[a-z][[:punct:]]/i", trim($_GET["id"]), $match); if…

NIST 发布后量子密码学转型战略草案

美国国家标准与技术研究所 (NIST) 发布了其初步战略草案&#xff0c;即内部报告 (IR) 8547&#xff0c;标题为“向后量子密码标准过渡”。 该草案概述了 NIST 从当前易受量子计算攻击的加密算法迁移到抗量子替代算法的战略。该草案于 2024 年 11 月 12 日发布&#xff0c;开放…

adb不识别设备(手机)的若干情形及解决方法

1.执行adb root 提示adb: unable to connect for root: no devices/emulators found&#xff1b; 执行adb devices ,List下无设备 原因&#xff1a;往往是数据线或USB插口问题&#xff0c;换根数据线或换个USB插口试试 2.执行adb devices List下提示 “592b925b no permi…

openai 论文Scaling Laws for Neural Language Models学习

2001.08361 (arxiv.org) 论文研究语言模型在交叉熵损失下的性能经验缩放定律&#xff1a;模型损失&#xff08;性能&#xff09;随模型大小、数据集大小和用于训练的计算量呈现缩放为幂律的关系&#xff0c;有些趋势跨越超过 7 个数量级。其他模型架构细节 &#xff08;如网络…

Go语言跨平台桌面应用开发新纪元:LCL、CEF与Webview全解析

开篇寄语 在Go语言的广阔生态中&#xff0c;桌面应用开发一直是一个备受关注的领域。今天&#xff0c;我将为大家介绍三款基于Go语言的跨平台桌面应用开发框架——LCL、CEF与Webview&#xff0c;它们分别拥有独特的魅力和广泛的应用场景。通过这三款框架&#xff0c;你将能够轻…

java小练习

小练1.用while语句计算11/2!1/3!1/4!...1/20!的和 public class test_11_17_2 {public static void main(String[] args) {double sum 0;double item 1;int n 20;int i 1;while(i<n){sum item;i i1;item item*(1.0/i);}System.out.println(sum);} } 小练2.计算88888…

Linux系统Centos设置开机默认root用户

目录 一. 教程 二. 部分第三方工具配置也无效 一. 教程 使用 Linux 安装Centos系统的小伙伴大概都知道&#xff0c;我们进入系统后&#xff0c;通常都是自己设置的普通用户身份&#xff0c;而不是 root 超级管理员用户&#xff0c;导致我们在操作文件夹时往往爆出没有权限&am…