【算法详解】力扣162.寻找峰值

本文主要是介绍【算法详解】力扣162.寻找峰值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目描述

力扣链接：力扣162.寻找峰值

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

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

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

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

二、思路分析

最简单的方法，直接使用std::max_element()寻找最大值，最大值一定是一个峰值。

class Solution {
public:int findPeakElement(vector<int>& nums) {return max_element(nums.begin(), nums.end()) - nums.begin();}
};

该方法是时间复杂度为O(N)，题目要求O(logN)，查找算法容易想到的是二分查找，该题也可以使用二分查找方法来求解。

二分查找的核心是当中间值满足条件时，就可以舍弃另一半，从而缩小范围。

题目中说可以假设 nums[-1] = nums[n] = -∞ 。那么说明首个元素nums[0]和最后一个元素nums[n-1]也可以是峰值。

那么对于二分查找的mid：

大于右边的值，那么左边一定有峰值；
反之，则右边一定有峰值

因此可以写出以下代码：

class Solution {
public:int findPeakElement(vector<int>& nums) {int n = nums.size();int left = 0, right = n - 1;while (left < right) {int mid = (left + right) >> 1; // 右移一位，相当于除以2if (nums[mid] > nums[mid + 1]) {right = mid;}else {left = mid + 1;}}return left;}
};