JAVA解决山脉数组的峰顶索引问题

JAVA解决山脉数组的峰顶索引问题

01 题目

符合下列属性的数组 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 = [1,3,5,4,2]
输出：2

示例 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
• 题目数据保证 arr 是一个山脉数组

02 知识点

• 二分查找
• 数组遍历

03 我的题解

public class erfen01 {

	public static void main(String[] args) {
		//测试数据
		int[] arr= {24,69,100,99,79,78,67,36,26,19};
		peakIndexInMountainArray(arr);
	}
	
	
	
	public static int peakIndexInMountainArray(int[] arr) {
//		由题设得山脉数组的峰值一定不在边缘，所以循环目标不包括边缘
		int left=1;
		int right=arr.length-2;
//		res用于记录峰值
		int res=-1;
//		二分查找是从中间往两边找的，当最右边的数小于最左边时，说明在该范围内没有找到目标
		while (left<=right) {
//			从中间左边加右边除以2开始找，用减法加的方式防止数组越界
			int mid=left+(right-left)/2;
			//由题设可知山脉数组的峰值大于两边，当查找值arr[mid]小于其中一边时，可以移动边界，缩小查找范围
			if (arr[mid]>arr[mid-1]&&arr[mid]>arr[mid+1]) {
				res=mid;
				break;
			}else if(arr[mid]>arr[mid-1]&&arr[mid]<arr[mid+1]) {
				left=mid+1;
			}else {
				right=mid-1;
			}
			
			
		}
		
		System.out.println(res);
		return res; 
    }
}