【二分查找】Leetcode 寻找峰值

题目解析

162. 寻找峰值

在这里插入图片描述
题目中有一个很重要的提示:对所有有效的i都存在nums[i] != nums[i+1],因此这道题不需要考虑nums[mid] 和 nums[mid+1]之间的相等与否的关系


算法讲解

1. 暴力枚举
我们按照顺序判断每个数字是否是当前的峰值,如果是直接返回,如果不是继续寻找。如果寻找的数组末尾还没有寻找到,那么就是数组的最后一个元素

2. 二分法

在这里插入图片描述
如果当前的nums[i] < nums[i+1] 说明i左侧不一定会出现峰值,因为它是上升趋势,峰值一定会出现在i+1的右侧区域

反之,如果当前的nums[i] > nums[i+1] 说明i左侧一定会出现峰值,但是i+1右侧不一定会出现,因为它是下降趋势的

又因为题目中说明没有一个合理的i,存在num[i] == nums[i+1],因此我们不需要对此情况进行判断

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            //左边一定存在峰值
            if(nums[mid] > nums[mid + 1])right = mid;
            //右边一定存在峰值
            if(nums[mid] < nums[mid + 1])left = mid + 1;
        }
        return left;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/527891.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【WEEK7】 【DAY1】索引【中文版】

2024.4.8 Monday 目录 7.索引7.1.内涵7.2.索引的作用7.3.索引的分类7.3.1.主键索引&#xff08;PRIMARY KEY&#xff09;7.3.1.1.主键 : 某一个属性组能唯一标识一条记录7.3.1.2.特点 : 7.3.2.唯一索引&#xff08;UNIQUE KEY&#xff09;7.3.2.1.作用 : 避免同一个表中某数据…

第一部分 Vue讲解(代码版)

1.第一个vue实例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-w…

获得乙级风力发电设计资质需要哪些注册工程师资格?

要获得乙级风力发电设计资质&#xff0c;通常需要以下注册工程师资格&#xff1a; 注册电气&#xff08;发输电&#xff09;工程师&#xff1a;他们负责风力发电项目的电气系统设计、优化、设备选型和配置&#xff0c;确保电力供应的安全性和可靠性。他们的专业知识对于保证风…

SpringBoot的旅游管理系统+论文+ppt+免费远程调试

项目介绍: 基于SpringBoot旅游网站 旅游管理系统 本旅游管理系统采用的数据库是Mysql&#xff0c;使用SpringBoot框架开发。在设计过程中&#xff0c;充分保证了系统代码的良好可读性、实用性、易扩展性、通用性、便于后期维护、操作方便以及页面简洁等特点。 &#xff08;1&…

吴恩达深度学习笔记:深层神经网络(Deep Neural Networks)4.5-4.8

目录 第一门课&#xff1a;神经网络和深度学习 (Neural Networks and Deep Learning)第四周&#xff1a;深层神经网络(Deep Neural Networks)4.5 为什么使用深层表示&#xff1f;&#xff08;Why deep representations?&#xff09; 第一门课&#xff1a;神经网络和深度学习 (…

5.网络编程-socker(golang版)

目录 一、什么是socket&#xff1f; 二、Golang中使用TCP TCP服务端 TCP客户端​​​​​​​ 三、TCP黏包&#xff0c;拆包 1.什么是粘包&#xff0c;拆包&#xff1f; 2.为什么UDP没有粘包&#xff0c;拆包&#xff1f; 3.粘包拆包发生场景 4.TCP黏包 黏包服务端 …

官宣定档“2024上海国际半导体产业展会”定于11月份在沪召开

2024上海国际半导体产业展览会 2024 Shanghai Semiconductor Expo 时间:2024年11月18-20日 地点:上海新国际博览中心 前言 近年来&#xff0c;上海半导体产业呈现出快速发展的态势。一方面&#xff0c;得益于国家政策的大力支持&#xff0c;上海半导体产业得到了迅猛的发展。…

计算机组成结构2

概念 存储系统 解决成本-速度-容量之前的矛盾问题 寄存器–cache–内存–硬盘–外存储 局部性原理 时间局部&#xff1a;相邻的时间访问同一个数据空间局部&#xff1a;相邻的空间地址会被连续访问 cache cpu与主存之间&#xff0c;命中cache后就不需要访问主存&#xff0c;…

景联文科技:为AI大模型提供高质海量训练数据

在全球AI浪潮的推动下&#xff0c;大量训练数据已成为AI算法模型发展和演进中的关键一环。 艾瑞咨询数据显示&#xff0c;包括数据采集、数据处理&#xff08;标注&#xff09;、数据存储、数据挖掘等模块在内的AI基础数据服务市场&#xff0c;将在未来数年内持续增长。 预计到…

跟着GPT学设计模式之适配器模式

题图来自APOD 你好&#xff0c;这里是codetrend专栏“跟着GPT学设计模式”。 说明 适配器模式&#xff08;Adapter Pattern&#xff09;是一种结构型设计模式&#xff0c;用于将一个类的接口转换为客户端所期望的另一个接口。适配器模式允许不兼容的接口协同工作&#xff0c…

面向跳转编程JOP问题及挑战

BTI分支目标识别精讲与实践系列 思考 1、什么是代码重用攻击?什么是ROP攻击?区别与联系? 2、什么是JOP攻击?间接分支跳转指令? 3、JOP攻击的缓解技术?控制流完整性保护? 4、BTI下的JOP如何缓解?什么是目标着陆台? 5、BTI的架构细节?硬件原理?间接分支类型?指…

数据库(mysql)-基本查询语句(DQL)

查询语句 这边查询是给予一定表格,这边先做个解释 教师表包括(name(姓名),gender(性别),salary(工资),title(职位),subject_id(课程的编号),comm(奖金)) 学生表包括(姓名(name),gender(性别),job(职位),生日(birth)) 模版 SELECT 字段名 FROM 查询表 WHERE 查询语句 或与非…

Laravel 项目如何运行

如有一个 Laravel 项目&#xff0c;在配置好 PHP 版本和运行环境后&#xff0c;可以直接在项目下直接运行&#xff1a; php artisan serve 来启动你的项目。 通过浏览器查看 当项目运行后&#xff0c;默认的启动端口为 8000&#xff0c;可以通过浏览器来进行查看运行的 Larav…

c++的学习之路:17、stack、queue与priority_queue

摘要 本文主要是介绍一下stack、queue、priority_queue的使用以及模拟实现&#xff0c;文章末附上代码以及思维导图。 目录 摘要 一、stack的介绍和使用 1、stack的介绍 2、stack的使用 3、stack的模拟实现 二、queue的介绍和使用 1、queue的介绍 2、queue的使用 3、…

leetcode刷题日记之接雨水问题

题目描述 解题思路 这个题目相当于一个桶的容量是多少&#xff0c;这取决于最短的模板的高度&#xff0c;&#xff0c;对于位置来讲&#xff0c;第i个位置所能承载的最大的容量为左右两侧最低的高度减去该位置的高度&#xff0c;如果两侧的最低位置小于height【i】&#xff0c…

TSINGSEE青犀边缘计算AI智能分析网关V4客流统计算法的配置步骤及使用

TSINGSEE青犀AI智能分析网关V4内置了近40种AI算法模型&#xff0c;支持对接入的视频图像进行人、车、物、行为、烟火等实时检测分析&#xff0c;上报识别结果&#xff0c;并能进行语音告警播放。硬件支持RTSP、GB28181协议、以及厂家私有协议接入&#xff0c;可兼容市面上常见的…

Python学习从0到1 day21 第二阶段 面向对象 ④ 类型注解

仗剑红尘已是癫&#xff0c;有酒平步上青天 —— 24.4.7 一、变量的类型注解 学习目标 1.理解为什么使用类型注解 2.掌握变量的类型注解语法 为什么使用类型注解 tip&#xff1a;CTRLP&#xff0c;可以提示函数中传入的参数 当我们需要使用pycharm的自动补全功能&#xff0c;又…

Java | Leetcode Java题解之第18题四数之和

题目&#xff1a; 题解&#xff1a; class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> quadruplets new ArrayList<List<Integer>>();if (nums null || nums.length < 4) {return…

(表征学习论文阅读)A Simple Framework for Contrastive Learning of Visual Representations

Chen T, Kornblith S, Norouzi M, et al. A simple framework for contrastive learning of visual representations[C]//International conference on machine learning. PMLR, 2020: 1597-1607. 1. 前言 本文作者为了了解对比学习是如何学习到有效的表征&#xff0c;对本文所…

Disk Drill Enterprise for Mac v5.5.1515数据恢复软件中文版

Disk Drill 是 Mac 操作系统固有的Mac数据恢复软件&#xff1a;使用 Recovery Vault 轻松保护文件免遭意外删除&#xff0c;并从 Mac 磁盘恢复丢失的数据。支持大多数存储设备&#xff0c;文件类型和文件系统。 软件下载&#xff1a;Disk Drill Enterprise for Mac v5.5.1515激…