山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。

class Solution {
public:
    int solve(int* a, int aLen) 
    {
        int i;
        for(i=aLen-1;i>0;i--)//从后向前遍历
        {
            if(a[i]>a[i-1])//大于前值，可能是峰值
            {
                if(i==aLen-1||a[i]>a[i+1]) //后边界或大于后值
                    return i; //中断输出 i
            }
         }
        return 0; //遍历完还没找到 说明单调减 返回头
        // write code here
    }
};

由于是线性遍历 最坏情况下需要遍历整个数组，时间复杂度

由于没有使用额外的空间 空间复杂度为
运行时间 3ms 占用内存 416KB

方法二：二分查找

先考虑找到任意一个峰值：

分析：数组两端认为是负无穷，而数组的值是确定的整型数，必然不会是正无穷，这说明数组中必定能找到一个峰值
证明很简单：左右两端都是负无穷，而数组中的数都大于负无穷，那么左端到数组是单调递增的，数组到右端是单调递减的，所以峰值必然存在
若峰值不止一个，我们随意找到一个就行，由此我们想到，因为数组中相邻两个数必然不同，我们可以将数组划分为若干个“山脉数组”，只有找到其中一个“山脉数组”的峰值即可，我们证明这种想法的可行性
换而言之，这种方法不会在有解的情况下查找不到解，先回顾“山脉数组”的二分解法：
若中点递增，说明极值点在右方
若中点递减，说明极值点在左方
在找到的峰值和右端点之间再次二分查找，至结果收敛，即可找到索引最大的峰值

按照如上的做法 当左右侧与中间导数都是大于零 即单调增场景下

无法判断峰值在那一侧

故使用

使之退化为遍历 保证答案正确性

class Solution {
public:
    int find(int* a,int left,int right)//二分法找峰值
    {
        if (a[right]>a[right-1])//特例 右节点是峰值 直接返回
            return right;
        int mid;
        while(left<right)
        {
            if (a[left]>a[left+1])//左节点是峰值 说不好
                mid=right-1;
            else
                mid = (left+right)/2;//二分
            if(a[mid]>a[mid + 1])//中间点导数为负 
                right = mid;//峰值在左侧
            else//否则
                left = mid + 1;//峰值在右侧
        }
        return right;
    }
    int solve(int* a, int aLen) {
        int ans=find(a,0,aLen-1),newans;
        while(1){//在已找到峰值的右侧继续二分查找 保证为最右侧峰值
            newans=find(a,ans,aLen-1);
            if(ans!=newans)//直至结果稳定
                ans=newans;
            else
                return ans;
        }
    }
};

时间复杂度  最好情况采用二分查找，复杂度是 最坏情况时间复杂度等于遍历是

空间复杂度：没有使用额外的空间 为

二分法能大大降低复杂度，要熟练化用掌握，但也要结合情况具体分析