0852. Peak Index in a Mountain Array

题目信息

题号:

0852

难度:

Medium

主题:

数组、山脉数组、峰顶下标

原题:

LeetCode 0852

重点:

输入保证先严格递增后严格递减,因此峰顶唯一且不在数组两端;返回从 0 开始的峰顶下标,并要求 O(log n) 时间

题目重述

给定一个山脉数组 arr。存在唯一的下标 i,满足 0 < i < arr.length - 1,数组从开头到 i 严格递增,并从 i 到末尾严格递减。

请返回这个唯一峰顶元素的下标 i。输入已经保证满足山脉数组定义,不需要处理不存在峰顶或含平台的情况;题目要求算法运行时间为 O(log n)。

3 <= arr.length <= 10^5,0 <= arr[i] <= 10^6。

自建示例

峰顶位于中间:

输入:arr = [0,2,5,3,1]
输出:2
解释:下标 2 的值 5 左侧严格递增,右侧严格递减,因此它是唯一峰顶。

最短山脉数组:

输入:arr = [2,9,1]
输出:1
解释:数组长度达到题目允许的最小值 3。中间元素 9 同时大于两侧元素,因此唯一峰顶下标为 1。