题目

描述

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

• 假设 nums[-1] = nums[n] = -∞。

方法一

思路

• 需要寻找索引最大的峰值，所有优先查找右边的峰值，即从数组的右边开始遍历；
• 遍历数组，寻找比其左右两边的数大的值，即为满足要求的峰值，返回该峰值即可；
• 注意题目中明确说明a[-1]，a[n]为最小值，所以对于边界值只需要比较一次就可以了。

具体步骤

• 代码如下

  import java.util.*;
  public class Solution {
  /**
  * 寻找最后的山峰
  * @param a int整型一维数组 
  * @return int整型
  */
  public int solve (int[] a) {
     // write code here
     if (a.length == 1 || a == null || a.length == 0){
         return 0;
     }
     // 从尾部开始查找
     int i = a.length-1;
     // a[n] 默认为最小值
     if (a[i] > a[i-1]){
         return i;
     }
     --i;
     // 遍历
     while(i > 0){
         if (a[i] > a[i+1] && a[i] > a[i-1]){
             return i;
         }
         --i;
     }
     // a[-1] 默认为最小值
     if (a[i] > a[i+1]){
         return i;
     }
     return 0;
  }
  }

• 时间复杂度：，遍历一遍数组；
• 空间复杂度：，常数级空间复杂度。

方法二

思路

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

具体步骤

• 参考下图栗子：
  
• 代码如下：

  import java.util.*;
  public class Solution {
  /**
  * 寻找最后的山峰
  * @param a int整型一维数组 
  * @return int整型
  */
  public int solve (int[] a) {
     // write code here
     if (a.length == 1 || a == null || a.length == 0){
         return 0;
     }
     for (int i = a.length-1; i >= 1; --i){
         if (a[i] >= a[i-1])
             return i;
     }
     return 0;
  }
  }

• 时间复杂度：，遍历一遍数组；
• 空间复杂度：，常数级空间复杂度。