力扣(LeetCode)164. 最大间距(C++)

news/2024/4/19 8:39:50/

桶排序(划分区间)

一次遍历找到区间内最大值 MaxMaxMax ,最小值 MinMinMin 。区间 (Min,Max](Min,Max](Min,Max] 左开右闭,划分为 n−1n-1n1 个长度为 lenlenlen 的区间 ,划分的区间左开右闭,所以每个子区间有 len−1len-1len1 个数。
根据实际意义,
(n−1)(len−1)≤Max−Min−1(n-1)(len-1)\le Max - Min -1(n1)(len1)MaxMin1 时,答案一定不在某个子区间内部取到。
整理上式,得,
len≤⌊Max−Min+n−2n−1⌋=⌈Max−Minn−1⌉len\le\lfloor\frac{Max-Min+n-2}{n-1}\rfloor=\lceil\frac{Max-Min}{n-1}\rceillenn1MaxMin+n2=n1MaxMinC++C++C++ 代码只使用不等式的前半段。

有了子区间的长度,数字就可以对应到子区间了。再次遍历 numsnumsnums ,维护每个子区间的最大值 maxmaxmax ,最小值 minminmin ,区间是否用到 usedusedused

最后遍历所有子区间,维护答案,即为所求。

class Solution {
public:int maximumGap(vector<int>& nums) {const int INF = 0x3f3f3f3f;struct Range{int min,max;bool used;Range () : min(INF) , max ( -INF) , used(false) {}};int n = nums.size();int Min = INF, Max = -INF;for(auto &x:nums){Min = Min<x?Min:x;Max = Max>x?Max:x;}if(nums.size()<2||Min==Max) return 0;vector<Range> r(n-1);int len = (Max - Min + n - 2) /(n-1);for(auto &x:nums){if( x == Min) continue;int i = (x - Min -1) / len;r[i].min = min(r[i].min,x);r[i].max = max(r[i].max,x);r[i].used = true;}int ans = 0 ;for(int i = 0,last = Min;i<n-1;i++){if(!r[i].used) continue;ans = max(ans,r[i].min - last);last = r[i].max;}return ans;}
};
  1. 时间复杂度 : O(n)O(n)O(n)nnn 是数字数量, 找出最大最小值,计算每个桶的最大最小值,遍历所有桶维护答案,总时间复杂度 O(3×n)O(3\times n)O(3×n) ,忽略常数时间复杂度 O(n)O(n)O(n)
  2. 空间复杂度 : O(n)O(n)O(n)n−1n-1n1 个桶的空间复杂度 O(n)O(n)O(n)

AC

AC

致语

  • 理解思路很重要!
  • 欢迎读者在评论区留言,墨染看到就会回复的。

http://www.ppmy.cn/news/4863.html

相关文章

Spring Boot的单元测试

⭐️前言⭐️ 一个Spring项目是有很多个功能的&#xff0c;如果想要单独测试某一个功能是否逻辑正确&#xff0c;就不能只依靠启动类来将整个项目启动去进行测试&#xff0c;而是要通过单元测试的方法&#xff0c;来单独的测试某一个功能&#xff0c;这篇文章就来介绍单元测试…

单例设计模式

文章目录前言一、单例模式饿汉模式懒汉模式二、线程安全问题前言 在有些系统中&#xff0c;为了节省内存资源、保证数据内容的一致性&#xff0c;对某些类要求只能创建一个实例&#xff0c;这就是所谓的单例模式。 一、单例模式 单类模式能够保证某个类在程序中只存在一个实…

YOLO系列目标检测算法——YOLOS

YOLO系列目标检测算法目录 - 文章链接 YOLO系列目标检测算法总结对比- 文章链接 YOLOv1- 文章链接 YOLOv2- 文章链接 YOLOv3- 文章链接 YOLOv4- 文章链接 Scaled-YOLOv4- 文章链接 YOLOv5- 文章链接 YOLOv6- 文章链接 YOLOv7- 文章链接 PP-YOLO- 文章链接 …

CY5-NHS酯zui大发射波长:662nm

水溶性CY5-COOH Cas:146368-11-8 CY5-NHS酯zui大发射波长&#xff1a;662nm 溶解性&#xff1a;易溶于有机溶剂&#xff08;DMF,DMSO和氯化物&#xff09;&#xff0c;难溶于水 质控&#xff1a;NMR 1H&#xff08;95%&#xff09;和13C,TLC&#xff0c;功能测试 光谱性质&…

Servlet生命周期和线程安全

✅作者简介&#xff1a;热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏&#xff1a;JAVA开发者…

C# 绘图基础

一 GDI技术简介 ① GDI&#xff1a;Graphics Device Interface. ② GDI&#xff1a;GDI的改进&#xff1b; ③ 是.NET框架结构的重要组成部分&#xff1b; ④ 和GDI一样它提供对二维图形图像的支持&#xff1b; 二 .NET 对GDI的封装 三 坐标系统 GDI的坐标系统&#xff1b; …

【Python机器学习】梯度下降法的讲解和求解方程、线性回归实战(Tensorflow、MindSpore平台 附源码)

需要全部源码请点赞关注收藏后评论区留言私信~~~ 基本思想 迭代关系式是迭代法应用时的关键问题&#xff0c;而梯度下降&#xff08;Gradient Descent&#xff09;法正是用梯度来建立迭代关系式的迭代法。 机器学习模型的求解一般可以表示为&#xff1a; 其中&#xff0c;f(x)…

拖动布局的两种方式

一种是弹窗的拖动布局&#xff0c;一种是非弹窗。 代码如下&#xff1a; 非弹窗&#xff1a;这里加载了一个本地的视频 import android.content.Context; import android.content.SharedPreferences; import android.os.Bundle; import android.view.MotionEvent; import an…

虚拟局域网

♥️作者&#xff1a;小刘在这里 ♥️每天分享云计算网络运维课堂笔记&#xff0c;疫情之下&#xff0c;你我素未谋面&#xff0c;但你一定要平平安安&#xff0c;一 起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的&#xff0c;绽放&#xff0c;…

CAN的信号结构

前言 CAN的通讯是基于帧传递的&#xff0c;CAN通讯的帧结构由以下七段组成&#xff1a;帧起始 仲裁段 控制段 数据段 CRC段 ACK段 帧结束 CAN的帧分为两种&#xff1a;标准帧和扩展帧&#xff0c;分别对应着两个不同的协议&#xff1a;CAN2.0A | CAN2.0B&#xff1b; 标准帧和…

Java try catch语句详解

在实际应用中&#xff0c;对于错误的处理是极其重要的&#xff0c;任何程序都很难做到百分百完美&#xff0c;程序中可能存在大量未知问题&#xff0c;所以程序开发时一定要对各种问题进行相应的处理&#xff0c;而 Java 提供的异常处理机制可以帮用户更好地解决这方面的问题。…

【网页制作课作业】用HTML+CSS制作一个简单的学校网页(9页)

&#x1f389;精彩专栏推荐 &#x1f4ad;文末获取联系 ✍️ 作者简介: 一个热爱把逻辑思维转变为代码的技术博主 &#x1f482; 作者主页: 【主页——&#x1f680;获取更多优质源码】 &#x1f393; web前端期末大作业&#xff1a; 【&#x1f4da;毕设项目精品实战案例 (10…

【Leetcode】单值二叉树、 相同的树、对称二叉树、另一颗树的子树、二叉树遍历、二叉树的前序遍历

文章目录OJ链接单值二叉树相同的树对称二叉树另一颗树的子树二叉树遍历二叉树的前序遍历OJ链接 1、【单值二叉树】OJ链接 2、【相同的树】OJ链接 3、【对称二叉树】OJ链接 4、【另一棵树的子树】OJ链接 5、【二叉树遍历】OJ链接 6、【二叉树的前序遍历】OJ链接 单值二叉树 >…

通俗易懂的java设计模式(3)-观察者设计模式

什么是观察者设计模式 观察者模式主要应用在对象存在一对多关系的情况下&#xff0c;那么如果一个对象&#xff0c;依赖于另一个对象&#xff0c;那个被依赖的对象一旦被修改&#xff0c;依赖于他的那个对象也会被观察者所告知。 观察者模式又被称作为发布-订阅模式&#xff0c…

Go语言基础函数学习

Go语言中的函数1. 函数2. defer语句3. 函数进阶4. 匿名函数5. 闭包6. 内置函数7. 函数的注意事项8. 自定义错误处理9. 字符串函数10. 日期和时间函数11. 输入输出1. 函数 基本结构 func 函数名(参数)(返回值){函数体 }函数的参数和返回值都是可选的 在调用有返回值的函数时&a…

小学生C++画图 Go C 编程 第8课 魔法计时器(魔法学院的奇幻之旅 Go C编程绘图)

Goc编程第一课 Goc编程第一课_哔哩哔哩_bilibili Goc编程第一课扩展加复习 Goc编程第一课扩展加复习_哔哩哔哩_bilibili Goc编程第二课 Goc编程第二课_哔哩哔哩_bilibili Goc编程第三课 Goc编程第三课_哔哩哔哩_bilibili Goc编程第四课 Goc编程第四课_哔哩哔哩_bilibili G…

【OpenCall】ICASSP2023通用会议理解及生成挑战赛邀请函

ICASSP2023 通用会议理解及生成挑战赛(General Meeting Understanding and Generation Challenge,缩写为 MUG)是ICASSP2023 系列大挑战(SPGC)之一&#xff0c;由魔搭ModelScope社区、阿里巴巴达摩院语音实验室&语言技术实验室&#xff0c;阿里云天池联合浙江大学数字媒体计…

ES迁移到OpenSearch

方式一&#xff1a;共享文件存储迁移 尽管可以使用 repository-s3 插件直接将快照生成到 S3&#xff0c;但必须在每个节点上安装此插件&#xff0c;调整 opensearch.yml&#xff08;如果使用的是 Elasticsearch 集群&#xff0c;则需要调整 elasticsearch.yml&#xff09;&…

10 个杀手级的 Python 自动化脚本

重复性任务总是耗时且无聊&#xff0c;想一想你想要一张一张地裁剪 100 张照片或 Fetch API、纠正拼写和语法等工作&#xff0c;所有这些任务都很耗时&#xff0c;为什么不自动化它们呢&#xff1f;在今天的文章中&#xff0c;我将与你分享 10 个 Python 自动化脚本。 所以&am…

【大数据入门核心技术-Kafka】(四)Kafka常用shell命令

目录 一、准备工作 1、Zookeeper集群安装 2、Kafka集群安装 二、常用Shell命令 1、创建Topic 2、查看创建的Topic 3、查看某一个Topic的详细信息 4、修改Topic 5、删除Topic 6、生产者发布消息命令 7、消费者接受消息命令 8、查看kafka节点数目 9、查看kafka进程 一…