可视化图解算法42：寻找峰值

牛客网 面试笔试TOP101            |             LeetCode 162. 寻找峰值

1. 题目

描述

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：

1≤nums.length≤2×105

-231<= nums[i] <= 231- 1

如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

示例1

输入：

[2,4,1,2,7,8,4]

返回值：

1

说明：

4和8都是峰值元素，返回4的索引1或者8的索引5都可以    

示例2

输入：

[1,2,3,1]

返回值：

2

说明：

3 是峰值元素，返回其索引 2    

2. 解题思路

题目限定了复杂度：O(logN)的时间复杂度。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。因此可以使用二分查找找到一组峰值，但该峰值不一定是最大值，满足题目要求。

具体思路为：

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372588

• Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367844

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364842

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @return int整型*/
func findPeakElement(nums []int) int {// 1. 定义变量left := 0right := len(nums) - 1// 2. 通过循环查找峰值for left < right {mid := (left + right) / 2 //计算中间位置if nums[mid] > nums[mid+1] {right = mid //mid开始 向左的位置区间中有峰值} else if nums[mid] < nums[mid+1] {left = mid + 1 //(mid+1)开始 向右的位置区间中有峰值} else {//根据题目规定：此种情况不存在，所以不进行任何操作}}return left  // 此时 left==right
}

• Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372588

• Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367844

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364842

4.小结

根据题目要求数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。因此可以使用二分查找找到一组峰值。定义两个变量left、right，分别指向数组的第0个位置和最后一个位置。这两个变量组成的区间为：[0,n]。通过循环缩小数组区间，直至找到峰值。

《数据结构与算法》深度精讲课程正式上线啦！七大核心算法模块全解析：

        ✅  链表

        ✅  二叉树

        ✅  二分查找、排序

        ✅  堆、栈、队列

        ✅  回溯算法

        ✅  哈希算法

        ✅  动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997

对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：莫笑农家腊酒浑，丰年留客足鸡豚。