讯享网

 <p id="34IB79DU">专栏：50多种数据结构彻底征服</p><p id="34IB79DV">专栏：50多种经典图论算法全部掌握</p><p id="34IB79E1">在职场中求职和招聘是双向的，而HR拒绝求职者都习以为常了，面试不通过连封邮件都不用发，而对于求职者拒绝HR发的offer，估计有些人可能还没经历过，希望以后大家每次找工作的时候都能经历，尽量让它成为常态。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1028%2F0216d614j00sm1ng7001hd200jc009kg00jc009k.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1028%2F1a44fb6aj00sm1ng80059d200u001uog00u001uo.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1028%2F902a9f63j00sm1ng9002sd200c000osg00c000os.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1028%2Fdj00sm1nga001yd200c000k7g00c000k7.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="34IB79EF">--------------下面是今天的算法题--------------</p><p id="34IB79EH">来看下今天的算法题，这题是LeetCode的第162题：寻找峰值。</p><p id="34IB79EL">问题描述</p><p id="34IB79ES">来源：LeetCode第162题<br/></p><p id="34IB79ET">难度：中等</p><p id="34IB79F1">峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。</p><p id="34IB79F3">数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。</p><p id="34IB79F5">你必须实现时间 复杂度为 O(log n) 的算法 来解决此问题。</p><p id="34IB79F7">示例1：<br/></p><p><br/><blockquote id="34IB79GO">输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。</blockquote><br/></p><p id="34IB79F8">示例2：<br/></p><p><br/><blockquote id="34IB79GP">输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。</blockquote><br/></p><p><ul><li id="34IB79GL"></p><p id="34IB79FA">1 &lt;= nums.length &lt;= 1000</p><p></li><li id="34IB79GM"></p><p id="34IB79FB">-2^31 &lt;= nums[i] &lt;= 2^31 - 1</p><p></li><li id="34IB79GN"></p><p id="34IB79FC">对于所有有效的 i 都有 nums[i] != nums[i + 1]</p><p></li></ul></p><p id="34IB79FG">问题分析</p><p id="34IB79FN">这题让找出数组中的峰值，因为nums[-1] = nums[n] = -∞ ，也就是默认数组两边的值（实际上是不存在的）是负无穷大，所以数组中肯定是有峰值的。如果没有时间复杂度的限制，这题就是一道非常简单的题，直接遍历数组中的每个值然后与两边比较即可。</p><p id="34IB79FP">但这题要求的时间复杂度是O(log n) ，所以我们只能使用二分查找，每次用中间的值nums[mid]和他的下一个值nums[mid+1]比较哪个大，因为提示中说了 对于所有有效的 i 都有 nums[i] != nums[i + 1] ，所以大的那边一定有峰值。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1028%2F08d00573j00sm1ngb0011d200hg00b1g00hg00b1.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="34IB79FS">JAVA：</p><pre></pre></p><p id="34IB79G0">C++：</p><pre></pre><br/></p><p id="34IB79G4">Python：</p><pre></pre></p><p id="34IB79GC"><strong>笔者简介</strong></p><p id="34IB79GD">博哥，真名：<strong>王一博</strong>，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。</p>