LeetCode 162. 寻找峰值

一、题目

1、题目描述

2、接口描述

​

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

    }
};

3、原题链接

二、解题报告

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;
    }
};