首页/新闻资讯/正文详情

Kimi LeetCode 164.最大间距 Java实现

发布时间:2026/9/27 22:45:37 来源:云帆数科 栏目:资讯中心
Kimi    LeetCode 164.最大间距 Java实现
LeetCode 164. 最大间距 — Java 实现题目要求返回数组在排序后相邻元素之间的最大差值。要求 O(n) 时间线性时间排序如桶排序。思路一桶排序推荐O(n)O(n)O(n)核心思想排序后的n个数有n-1个间隔。设minVal、maxVal则最大间距的下界为\textit{lowerBound} \left\lceil \frac{\textit{maxVal} - \textit{minVal}}{n - 1} \right\rceil让每个桶的宽度等于lowerBound则同一个桶内的任意两数之差一定小于lowerBound所以最大间距不可能出现在同一个桶内只可能出现在相邻桶之间前一个桶的最大值与后一个桶的最小值之差。importjava.util.Arrays;classSolution{publicintmaximumGap(int[]nums){intnnums.length;if(n2)return0;intminValArrays.stream(nums).min().getAsInt();intmaxValArrays.stream(nums).max().getAsInt();if(minValmaxVal)return0;// 桶宽度 最大间距的下界intbucketSizeMath.max(1,(maxVal-minVal)/(n-1));// 桶数量 数值范围 / 桶宽度 1intbucketCount(maxVal-minVal)/bucketSize1;// 每个桶只记录最小值、最大值、是否为空int[]bucketMinnewint[bucketCount];int[]bucketMaxnewint[bucketCount];boolean[]hasNumnewboolean[bucketCount];for(intnum:nums){intidx(num-minVal)/bucketSize;if(!hasNum[idx]){bucketMin[idx]bucketMax[idx]num;hasNum[idx]true;}else{bucketMin[idx]Math.min(bucketMin[idx],num);bucketMax[idx]Math.max(bucketMax[idx],num);}}// 遍历非空桶计算前一个非空桶的最大值与当前桶的最小值之差intmaxGap0;intprevMaxminVal;for(inti0;ibucketCount;i){if(!hasNum[i])continue;maxGapMath.max(maxGap,bucketMin[i]-prevMax);prevMaxbucketMax[i];}returnmaxGap;}}时间复杂度O(n)空间复杂度O(n)思路二直接排序O(nlog⁡n)O(n \log n)O(nlogn)如果不追求线性时间一行排序即可importjava.util.Arrays;classSolution{publicintmaximumGap(int[]nums){if(nums.length2)return0;Arrays.sort(nums);intmaxGap0;for(inti1;inums.length;i){maxGapMath.max(maxGap,nums[i]-nums[i-1]);}returnmaxGap;}}关键点总结鸽巢原理n个数分布在(max-min)的范围里最大间距至少是(max-min)/(n-1)这是桶宽的来源。为什么只比较相邻非空桶同桶内差值 桶宽 ≤ 答案下界不可能是最优解因此最大间距只可能跨桶产生。桶内只需存 min/max无需真正排序桶内元素。示例nums [3,6,9,1]→ 排序后为[1,3,6,9]最大间距为39-6✅

相关推荐

一文讲透 .claude/ 文件夹:Claude Code 团队配置指南和最佳实践(TaoToken 统一 Key 接入版)
一文讲透 .claude/ 文件夹:Claude Code 团队配置指南和最佳实践(TaoToken 统一 Key 接入版)

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 22:45:37

大模型的实践应用40-用Qwen3(72B)+langchain+MCP+RAG搭建数学教学管理与成绩提升系统:从config.toml骨架到成绩预测验证
大模型的实践应用40-用Qwen3(72B)+langchain+MCP+RAG搭建数学教学管理与成绩提升系统:从config.toml骨架到成绩预测验证

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 22:45:31

Kimi    LeetCode 162.寻找峰值 Java实现
Kimi LeetCode 162.寻找峰值 Java实现

LeetCode 162. 寻找峰值 — Java 实现 思路一:二分查找(推荐)O(log⁡n)O(\log n)O(logn) 关键性质:数组相邻元素互不相同(nums[i] ! nums[i1]),且边界满足 nums[-1] nums[n] -∞,所… · 2026/9/27 22:45:31

不懂代码?科协网站页建设的意义保姆级建站教程
不懂代码?科协网站页建设的意义保姆级建站教程

不懂代码?科协网站页建设的意义保姆级建站教程 自己不会代码想做网站?别慌,这行我干了十年,见过太多人被“技术门槛”吓退。其实只要路子对,普通人也能搞出像样的站点。 这篇 保姆级建站教程… · 2026/9/27 23:27:20

RK3588移植Ubuntu 24.04:根文件系统与WiFi驱动深度适配指南
RK3588移植Ubuntu 24.04:根文件系统与WiFi驱动深度适配指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:27:14

Creo Aerospace装配建模二次开发:Python脚本驱动批量装配与BOM导出
Creo Aerospace装配建模二次开发:Python脚本驱动批量装配与BOM导出

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:27:14

热轧带钢缺陷检测:轻量化YOLO与产线级预处理实战
热轧带钢缺陷检测:轻量化YOLO与产线级预处理实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:27:14

2026硬件面试高频考点:ADC采样、EMC共模电流与光耦隔离设计
2026硬件面试高频考点:ADC采样、EMC共模电流与光耦隔离设计

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:27:14

嵌入式开发必会:烧录下载与仿真调试工具链全解析
嵌入式开发必会:烧录下载与仿真调试工具链全解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:27:14

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码