当前位置: 首页 > news >正文

Leetcode 寻找峰值

在这里插入图片描述

为了实现时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn),可以使用二分查找法:

解题思路:

  1. 峰值的特性是:当前元素大于左右相邻元素。
  2. 使用二分法:
    • 如果 nums[mid] > nums[mid + 1],说明峰值在左侧或当前 mid 位置(包括 mid),因此将 right = mid
    • 否则峰值在右侧,因此将 left = mid + 1
  3. 不断收缩区间,直到 left == right,此时即找到峰值。

时间复杂度:

  • 时间复杂度:(O(\log n)),因为每次迭代都将搜索范围减半。
  • 空间复杂度:(O(1)),不需要额外的空间。

java 实现

class Solution {public int findPeakElement(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;// 如果中点比右侧元素大,说明峰值在左侧(包括mid)if (nums[mid] > nums[mid + 1]) {right = mid;} else { // 否则峰值在右侧left = mid + 1;}}// 最终left和right会相遇,此时即为峰值位置return left;}
}

数组即便不是有序的,为什么仍然二分查找仍然可以找到峰值?

这是因为这道题的二分查找并不依赖于数组是否有序,而是利用了“峰值”的定义和数组的局部特性。

关键点

  1. 题目定义的峰值条件

    • 峰值是指某个元素严格大于其左右邻居的元素。
    • 如果一个元素 nums[mid] > nums[mid + 1],那么在 mid 或者其左侧一定存在一个峰值。
    • 如果 nums[mid] < nums[mid + 1],那么在 mid 的右侧一定存在一个峰值。
  2. 为什么可以二分?
    二分查找的核心在于:

    • 每次选择一个中间点 mid,并根据某个条件判断下一个搜索范围。
    • 在这道题中,“峰值”可以通过比较 nums[mid]nums[mid + 1] 来判断范围:
      • 如果 nums[mid] > nums[mid + 1]
        • 峰值在左侧或就是 mid,因为 mid 本身比右边的大(局部性质),可以舍弃右侧部分。
      • 如果 nums[mid] < nums[mid + 1]
        • 峰值一定在右侧,因为右边存在一个更大的值,最终会到达一个下降点形成峰值。

    这利用了“递增到下降”的局部特性来缩小搜索范围。

  3. 数学直观解释

    • 假设数组中不存在连续相等的数字(即没有平缓区域),并且在数组两端可以假想有值为负无穷的元素(题目已假设 nums[-1] = nums[n] = -∞)。
    • 在数组中总能找到一个峰值元素,原因是:
      • 如果数组中存在一个“上升”趋势,例如 nums[i] < nums[i+1],那么在右侧一定有一个峰值。
      • 如果数组中存在一个“下降”趋势,例如 nums[i] > nums[i+1],那么左侧也一定存在一个峰值。

    这种趋势保证了每次二分缩小范围后,最终一定会收敛到某个峰值点。

  4. 非有序数组的适用性
    题目并没有要求数组有序。因为峰值是局部性质(仅与相邻元素有关),只需要每次确定搜索方向,而不是依赖整体有序性。二分查找法的效率仍然得以保证。


举例说明

以数组 nums = [1, 2, 1, 3, 5, 6, 4] 为例:

  • 初始:
    • left = 0, right = 6,取中间点 mid = 3nums[mid] = 3
    • 比较 nums[mid]nums[mid + 1]3 < 5,说明右侧有峰值,更新 left = mid + 1
  • 第二轮:
    • left = 4, right = 6,取中间点 mid = 5nums[mid] = 6
    • 比较 nums[mid]nums[mid + 1]6 > 4,说明左侧有峰值,更新 right = mid
  • 第三轮:
    • left = 4, right = 5,取中间点 mid = 4nums[mid] = 5
    • 比较 nums[mid]nums[mid + 1]5 < 6,说明右侧有峰值,更新 left = mid + 1
  • 最终:
    • left = right = 5,返回 5,此时峰值为 6

总结

二分查找法在这道题中能用,是因为:

  1. 峰值的定义是局部性质,不依赖数组整体有序性。
  2. 每次比较中点和其右侧元素,可以有效缩小搜索范围。
  3. 这种方法本质上是利用数组的递增和递减趋势来确定峰值位置。

相关文章:

Leetcode 寻找峰值

为了实现时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)&#xff0c;可以使用二分查找法&#xff1a; 解题思路&#xff1a; 峰值的特性是&#xff1a;当前元素大于左右相邻元素。使用二分法&#xff1a; 如果 nums[mid] > nums[mid 1]&#xff0c;说明峰值在左侧或当前…...

探索大规模语言模型(LLM)在心理健康护理领域中的应用与潜力

概述 心理健康是公共卫生最重要的领域之一。根据美国国家精神卫生研究所&#xff08;NIMH&#xff09;的数据&#xff0c;到 2021 年&#xff0c;22.8% 的美国成年人将患上某种形式的精神疾病。在全球范围内&#xff0c;精神疾病占非致命性疾病负担的 30%&#xff0c;并被世界…...

Infisical开源密钥管理平台实战指南

1. 引言 在现代软件开发中,安全地管理环境变量和敏感信息已成为一个关键挑战。Infisical作为一个开源的密钥管理平台,为这一问题提供了强大而灵活的解决方案。本指南将深入探讨Infisical的功能,并通过实际操作步骤,帮助读者全面了解和使用这个工具。 2. Infisical概述 I…...

AI大模型:重塑软件开发流程与模式

人工智能技术的飞速发展&#xff0c;尤其是AI大模型的兴起&#xff0c;正以前所未有的速度和深度影响着各行各业&#xff0c;其中软件开发领域尤为显著。AI大模型&#xff0c;如GPT系列、BERT、Claude等通过其强大的自然语言处理能力、代码理解和生成能力&#xff0c;正在从根本…...

AMD(Xilinx) FPGA配置Flash大小选择

目录 1 FPGA配置Flash大小的决定因素2 为什么选择的Flash容量大小为最小保证能够完成整个FPGA的配置呢&#xff1f; 1 FPGA配置Flash大小的决定因素 在进行FPGA硬件设计时&#xff0c;选择合适的配置Flash是我们进行硬件设计必须考虑的&#xff0c;那么配置Flash大小的选择由什…...

基于Java Springboot图书借阅系统

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…...

DDRPHY数字IC后端设计实现系列专题之数字后端floorplanpowerplan设计

3.2.3 特殊单元的布局 布图阶段除了布置 I/O 单元和宏单元&#xff0c;在 28nm 制程工艺时&#xff0c;还需要处理两种特 殊的物理单元&#xff0c;Endcap 和 Tapcell。 DDRPHY数字IC后端设计实现系列专题之后端设计导入&#xff0c;IO Ring设计 &#xff08;1&#xff09;拐…...

【Mysql】Mysql函数(上)

1、概述 在Mysql中&#xff0c;为了提高代码重用性和隐藏实现细节&#xff0c;Mysql提供了很多函数。函数可以理解为封装好的模块代码。 2、分类 在Mysql中&#xff0c;函数非常多&#xff0c;主要可以分为以下几类&#xff1a; &#xff08;1&#xff09;聚合函数 &#xf…...

Java连接MySQL(测试build path功能)

Java连接MySQL&#xff08;测试build path功能&#xff09; 实验说明下载MySQL的驱动jar包连接测试的Java代码 实验说明 要测试该情况&#xff0c;需要先安装好MySQL的环境&#xff0c;其实也可以通过测试最后提示的输出来判断build path是否成功&#xff0c;因为如果不成功会直…...

卡尔曼滤波器

卡尔曼滤波器概述 卡尔曼滤波器&#xff08;Kalman Filter&#xff09;是一种递归的最优估计方法&#xff0c;广泛应用于信号处理、控制理论、导航定位等领域。它基于线性动态系统模型&#xff0c;通过观测数据不断更新系统的状态估计&#xff0c;从而使得估计值能够在噪声干扰…...

基于BERT的情感分析

基于BERT的情感分析 1. 项目背景 情感分析&#xff08;Sentiment Analysis&#xff09;是自然语言处理的重要应用之一&#xff0c;用于判断文本的情感倾向&#xff0c;如正面、负面或中性。随着深度学习的发展&#xff0c;预训练语言模型如BERT在各种自然语言处理任务中取得了…...

推荐15个2024最新精选wordpress模板

以下是推荐的15个2024年最新精选WordPress模板&#xff0c;轻量级且SEO优化良好&#xff0c;适合需要高性能网站的用户。中文wordpress模板适合搭建企业官网使用。英文wordpress模板&#xff0c;适合B2C网站搭建&#xff0c;功能强大且兼容性好&#xff0c;是许多专业外贸网站的…...

AWTK-WIDGET-WEB-VIEW 实现笔记 (2) - Windows

在 Windows 平台上的实现&#xff0c;相对比较顺利&#xff0c;将一个窗口嵌入到另外一个窗口是比较容易的事情。 1. 创建窗口 这里有点需要注意&#xff1a; 父窗口的大小变化时&#xff0c;子窗口也要跟着变化&#xff0c;否则 webview 显示不出来。创建时窗口的大小先设置…...

Linux四剑客及正则表达式

正则表达式 基础正则&#xff08;使用四剑客命令时无需加任何参数即可使用&#xff09; ^ # 匹配以某一内容开头 如&#xff1a;^grep匹配所有以grep开头的行。 $ # 匹配以某一内容结尾 如&#xff1a;grep$ 匹配所有以grep结尾的行。 ^$ # 匹配空行。 . # 匹配…...

ALS 推荐算法案例演示(python)

数学知识补充&#xff1a;矩阵 总结来说&#xff1a; Am*k X Bk*n Cm*n ----至于乘法的规则,是数学问题, 知道可以乘即可,不需要我们自己计算 反过来 Cm*n Am*k X Bk*n ----至于矩阵如何拆分/如何分解,是数学问题,知道可以拆/可以分解即可 ALS 推荐算法案例&#xff1a;电影推…...

labview中连接sql server数据库查询语句

当使用数据库查询功能时&#xff0c;我们需要用到数据库的查询语句&#xff0c;这里已调用sql server为例&#xff0c;我们需要按照时间来查询&#xff0c;这里在正常调用数据库查询语句时&#xff0c;我们需要在前面给他加一个限制条件这里用到了&#xff0c;数据库的查询语句…...

leetcode_二叉树最大深度

对二叉树的理解 对递归调用的理解 对内存分配的理解 基础数据结构&#xff08;C版本&#xff09; - 飞书云文档 每次函数的调用 都会进行一次新的栈内存分配 所以lmax和rmax的值不会混在一起 /*** Definition for a binary tree node.* struct TreeNode {* int val;* …...

Elasticsearch 重建索引 数据迁移

Elasticsearch 重建索引 数据迁移 处理流程创建临时索引数据迁移重建索引写在最后 大家都知道&#xff0c;es的索引创建完成之后就不可以再修改了&#xff0c;包括你想更改字段属性或者是分词方式等。那么随着业务数据量的发展&#xff0c;可能会出现需要修改索引&#xff0c;或…...

2411rust,异步函数

原文 Rust异步工作组很高兴地宣布,在实现在特征中使用异步 fn的目标方面取得了重大进度.将在下周发布稳定的Rust1.75版,会包括特征中支持impl Trait注解和async fn. 稳定化 自从RFC#1522在Rust1.26中稳定下来以来,Rust就允许用户按函数的返回类型(一般叫"RPIT")编…...

前端网络性能优化问题

DNS预解析 DNS 解析也是需要时间的&#xff0c;可以通过预解析的⽅式来预先获得域名所对应的 IP。 <link rel"dns-prefetch" href"//abcd.cn"> 缓存 强缓存 在缓存期间不需要请求&#xff0c; state code 为 200 可以通过两种响应头实现&#…...

优选算法——双指针

前言 本篇博客为大家介绍双指针问题&#xff0c;它属于优选算法中的一种&#xff0c;也是一种很经典的算法&#xff1b;算法部分的学习对我们来说至关重要&#xff0c;它可以让我们积累解题思路&#xff0c;同时也可以大大提升我们的编程能力&#xff0c;本文主要是通过一些题…...

【Rabbitmq篇】RabbitMQ⾼级特性----消息确认

目录 前言&#xff1a; 一.消息确认机制 • ⾃动确认 • ⼿动确认 手动确认方法又分为三种&#xff1a; 二. 代码实现&#xff08;spring环境&#xff09; 配置相关信息&#xff1a; 1&#xff09;. AcknowledgeMode.NONE 2 &#xff09;AcknowledgeMode.AUTO 3&…...

开源TTS语音克隆神器GPT-SoVITS_V2版本地整合包部署与远程使用生成音频

文章目录 前言1.GPT-SoVITS V2下载2.本地运行GPT-SoVITS V23.简单使用演示4.安装内网穿透工具4.1 创建远程连接公网地址 5. 固定远程访问公网地址 前言 本文主要介绍如何在Windows系统电脑使用整合包一键部署开源TTS语音克隆神器GPT-SoVITS&#xff0c;并结合cpolar内网穿透工…...

【idea】更换快捷键

因为个人习惯问题需要把快捷键替换一下。我喜欢用CTRLD删除一下&#xff0c;用CTRLY复制一样。恰好这两个快捷键需要互换一下。 打开file——>setting——>Keymap——>Edit Actions 找到CTRLY并且把它删除 找到CTRLD 并且把它删除 鼠标右键添加CTRLY 同样操作在Delet…...

最小的子数组(leetcode 209)

给定一个正整数数组&#xff0c;找到大于等于s的连续的最小长度的区间。 解法一&#xff1a;暴力解法 两层for循环&#xff0c;一个区间终止位置&#xff0c;一个区间起始位置&#xff0c;找到大于等于s的最小区间长度&#xff08;超时了&#xff09; 解法二&#xff1a;双指…...

IDEA-Plugins无法下载插件(网络连接问题-HTTP Proxy Settings)

IDEA-Plugins无法下载插件&#xff08;网络连接问题&#xff09; 改成如下配置&#xff1a; 勾选 添这个url即可&#xff1a;https://plugins.jetbrains.com/ 重启插件中心&#xff0c;问题解决。...

AWTK-WIDGET-WEB-VIEW 发布

awtk-widget-web-view 是通过 webview 提供的接口&#xff0c;实现的 AWTK 自定义控件&#xff0c;使得 AWTK 可以方便的显示 web 页面。 项目网址&#xff1a; https://gitee.com/zlgopen/awtk-widget-web-view webview 提供了一个跨平台的 webview 接口&#xff0c;是一个非…...

Mysql每日一题(if函数)

两种写法if()和case if()函数 select *,if(T.xT.y>T.z and T.xT.z>T.y and T.yT.z>T.x,Yes,No) as triangle from Triangle as T; case方法 select *, case when T.xT.y>T.z and T.xT.z>T.y and T.yT.z>T.x then Yes else No end as triangle from Trian…...

Spring Cloud Alibaba [Gateway]网关。

1 简介 网关作为流量的入口&#xff0c;常用功能包括路由转发、权限校验、限流控制等。而springcloudgateway 作为SpringCloud 官方推出的第二代网关框架&#xff0c;取代了Zuul网关。 1.1 SpringCloudGateway特点: &#xff08;1&#xff09;基于Spring5&#xff0c;支持响应…...

【动手学深度学习Pytorch】2. Softmax回归代码

零实现 导入所需要的包&#xff1a; import torch from IPython import display from d2l import torch as d2l定义数据集参数、模型参数&#xff1a; batch_size 256 # 每次随机读取256张图片 train_iter, test_iter d2l.load_data_fashion_mnist(batch_size) # 将展平每个…...