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

2023-12-24 17:37:10

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; 
    }
}

文章来源:https://blog.csdn.net/2302_77182979/article/details/135183646
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。