leetcode 852. 山脉数组的峰顶索引（二分查找）

这是我参与更文挑战的第15天
，活动详情查看更文挑战

题目

符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3
存在 i（0 < i < arr.length – 1）使得：

• arr[0] < arr[1] < … arr[i-1] < arr[i]
• arr[i] > arr[i+1] > … > arr[arr.length – 1]

给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i – 1] < arr[i] > arr[i + 1] > … > arr[arr.length – 1] 的下标 i 。

• 示例 1：

输入：arr = [0,1,0]
输出：1

• 示例 2：

输入：arr = [0,2,1,0]
输出：1

• 示例 3：

输入：arr = [0,10,5,2]
输出：1

• 示例 4：

输入：arr = [3,4,5,1]
输出：2

• 示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2
 

提示：

• 3 <= arr.length <= 104
• 0 <= arr[i] <= 106

一次遍历

找出第一个递减的转折点，该转折点的前一个下标即为山峰

代码

class Solution {
    public int peakIndexInMountainArray(int[] arr) {

        for (int i=1;i<arr.length;i++)
        {
            if(arr[i]<arr[i-1])
                return i-1;
        }
        return -1;
        
    }
}
复制代码

二分法

利用题目发现如下性质：由于 arr 数值各不相同，因此峰顶元素左侧必然满足严格单调递增，峰顶元素右侧必然不满足。

该数组是山峰数组，可以将顶点的左右两侧分为上坡和下坡，上坡是递增数组，下坡是递减数组，因此可以以下条件进行二分查找，

• 如果arr[mid]>arr[mid-1]说明当前区间[l,mid]都是递增数组，因此顶点只会出现在[mid+1,r]区间，
• 如果arr[mid]<arr[mid-1]说明当前区间[mid,r]都是递减数组，因此顶点只会出现在[l,mid-1]区间，

代码

class Solution {
    public int peakIndexInMountainArray(int[] arr) {

      int l=1,r=arr.length-2;
      while (l<=r)
      {
          int mid=(r-l)/2+l;
         if(arr[mid]>arr[mid-1])
              l=mid+1;
          else r=mid-1;
      }
      return r;

    }
}
复制代码