题解 | #寻找峰值#

算法思想一：遍历+峰值对比

解题思路：

1、找到索引最大的那个山峰元素并返回其索引，考虑从后往前遍历
2、假设 $nums[-1] = nums[n] = -∞$ ，需要对端点做处理
即：在对于数组的最后一个值，只需要考虑是否大于等于前面一个值，代码如( $i==n$ && $a[i]>=a[i-1]$ )，对于数组的第一个值，只需要考虑是否大于后面一个值，代码如( $i==0$ && $a[i]>=a[i+1]$ )，对于其他情况，判断某一个值是否大于等于左右两个值，代码如 $a[i-1]>=a[i]$ && $a[i-1]>=a[i-2]$

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    /**
     * 寻找最后的山峰
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int[] a) {
        // write code here
        int n = a.length-1;
        // 倒序遍历
        for(int i=n;i>=0;i--){
            // 索引为 0 n的特殊情况
            if((i==n&&a[i]>=a[i-1])||(i==0&&a[i]>=a[i+1])){
                return i;
                // 其他区域峰值
            }else if(a[i-1]>=a[i]&&a[i-1]>=a[i-2]){
                return i-1;
            }

        }
        return -1;
    }
}

复杂度分析

时间复杂度 $O(N)$ ： $N$ 表示数组的长度，遍历一遍数组时间 $O(N)$

空间复杂度 $O(1)$ ：仅使用一个常数级变量空间

算法思想二：方法一优化

解题思路：

方法一中除边界外，其余值均比较了两次，忽略了一个性质，即若从右往左遍历，当下标index处的值不是峰值时，其必满足 $a[index]<a[index-1]$ ,所以当检测index-1处是否为峰值时只需要与左边的值进行比较。
图解：

*
*

代码展示：

Python版本

class Solution:
    def solve(self , a ):
        # write code here
        # 倒序遍历
        for i in range(len(a)-1, -1, -1):
            # a[i] > a[i-1] 即为最大索引峰值
            if a[i] > a[i-1]:
                return i
        # 如果没有则返回数组最后位的索引
        return len(a)-1

复杂度分析

时间复杂度 $O(N)$ ：N表示数组的长度，遍历一遍数组时间 $O(N)$

空间复杂度 $O(1)$ ：仅使用常数级变量空间