题意概述

• 给定一个任意两个相邻元素值不相等数组
• 要求返回索引最大的那个山峰元素的索引
• 山峰元素是指其值大于或等于左右相邻值的元素。

方法一：逆序遍历

思路与具体做法

• 逆序遍历整个数组，遇到到的第一个山峰元素即为索引最大的那个山峰元素

class Solution {
public:
    int solve(int* a, int aLen){
		for(int i=aLen-1;i>=1;i--){
			if(a[i]>a[i-1])return i;
		} 
		return 0;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，逆序遍历整个数组
• 空间复杂度：$O\left(1\right)O(1)$O(1)，没有使用额外的空间

方法二：二分查找

思路与具体做法

• 缩小区间，不断在找到的峰值与右端点间二分查找，直到只有最右侧一个峰值为止
• 查找过程中
  • 若最右侧出现山峰，直接返回
  • 若最左侧出现山峰,且最右侧未出现山峰，则向左缩小区间
  • 若区间中点处于上坡，则向右走
  • 若区间中点处于下坡，则向左走

class Solution {
public:
	int BinarySearch(int* a,int l,int r){
		while(l<r){			
            int  mid=l+(r-l)/2;
            if(a[r]>a[r-1])return r;//最右侧出现山峰，直接返回
            else if(a[l]>a[l+1])mid=r-1;//最左侧出现山峰,且最右侧未出现山峰，则向左缩小区间
			if(a[mid]>a[mid+1])r=mid;//下坡，往左走 
			else l=mid+1;//上坡，往右走 
		}
		return r; 
	}
    int solve(int* a, int aLen){
    	int ans=BinarySearch(a,0,aLen-1),temp;//在当前区间查找一个峰值 
		while(temp=BinarySearch(a,ans,aLen-1),temp!=ans){//缩小区间后再次查找峰值，若峰值不相等，则反复缩小区间，直到锁定一个峰值为止 
			ans=temp;//缩小区间 
		} 
		return ans;//返回所在索引 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：最好情况二分查找，复杂度$O\left(2_{}n\right)O(\backslash log\_\{2\}\{n\}\; )$O(log2​n)，最坏情况遍历数组，复杂度$O\left(n\right)O(n)$O(n)
• 空间复杂度：$O\left(1\right)O(1)$O(1)，没有使用额外的空间