【刷题笔记6】LeetCode 162. 寻找峰值（二分查找优化）

用分享的方式成长，用有趣的眼光看世界。 

欢迎来到12 26 25的博客 ！
热爱编码、算法、知识总结，不定期更新有趣、有料、有营养内容。 让我们共同学习，共同进步。

系列索引 ： 【刷题笔记0】系列目录索引（持续更新 & 推荐收藏）

本题题目： LeetCode 162. 寻找峰值

分类：二分查找， 思维

难度： 中等

老规矩，先上AC图：

题目：162. 寻找峰值（点击直达原网站）

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

题解：

首先读题，题目中给到的序列是一个无需数组，同时有多个峰值，而我们只需要找到一个即可。另外丢复杂度要求是logN。

分析题意，我们不一定需要遍历所有元素，只要确定到峰值即可，同时logN第一反应就是二分（查分）法。

所以确定下来之后对于二分查找，明确两点 1. 明确终止条件 2. 确定子序列范围（边界）

1. 首先终止条件是找到波峰，返回波峰位置。那么如何确定波峰，就需要和左右两点分别进行比较。但这里有特殊情况

• 当序列（子序列）只剩一个值是什么情况？
• 注意比较时，遇到边界情况如何处理。

2. 根据当前点mid 的情况分析更大点所在区间，进而更新left和right的情况。

时间复杂度： O(logN)；  空间复杂度： O(1).

代码如下：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left != right){
            int mid = (left + right) / 2;
            if(nums[mid] > nums[mid + 1]) {
                if(mid == left) return mid;
                else if(nums[mid] > nums[mid - 1]) return mid;
                else right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
};

​

 上一篇： 从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密

下一篇： 400+条实用C/C++框架、库、工具整理 ，你能想到的都在这里了

如果有什么要补充的，欢迎下方👇评论区留言~

1份赞许 = 100分的认可，如果感觉还不错，点个赞👍 支持一下吧 ~

不定期分享 有趣、有料、有营养内容，欢迎 订阅关注 🤝 我的博客 ，期待在这与你相遇 ~