LeetCode 162. 寻找峰值

一、题目

1、题目描述

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

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

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

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

2、接口描述

?

class Solution {
public:
    int findPeakElement(vector<int>& nums) {

    }
};

3、原题链接

162. 寻找峰值

---

二、解题报告

1、思路分析

显然我们只需要找到一个极大值并返回下标即可。

对于寻找极值的常用方法是梯度下降法，这在深度学习中经常用到。

对于本题，我们只要沿着梯度上升的方向走即可。

我们取左右边界l,r，中点mid

如果grad(mid,r) < 0，r = mid

否则l = mid + 1

沿着梯度上升方向最终到达梯度为0的点即为局部极大值

2、复杂度

时间复杂度：O(logn) 空间复杂度：O(1)

3、代码详解

?

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
       int n = nums.size();
       auto num = [&](int idx) -> long long{
           if(idx == -1 || idx == n) return LLONG_MIN;
           return nums[idx];
       } ;
       int l = 0 , r = n - 1;
       while(l < r)
       {
           int mid = l + r >> 1;
           if(num(mid) > num(mid + 1)) r = mid;
           else l = mid + 1;
       }
       return l;
    }
};