0852. Peak Index in a Mountain Array¶
题目信息¶
- 题号:
0852
- 难度:
Medium
- 主题:
数组、山脉数组、峰顶下标
- 原题:
- 重点:
输入保证先严格递增后严格递减,因此峰顶唯一且不在数组两端;返回从 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。