题目难度: 简单
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
符合下列属性的数组 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 <= 10^4
- 0 <= arr[i] <= 10^6
- 题目数据保证 arr 是一个山脉数组
进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
题目思考
- 如何利用题目给出的条件优化时间复杂度?
解决方案
思路
- 分析题目, 一个最直接的思路就是从下标 1 开始遍历数组到下标 n-2, 返回同时大于左右邻居值的下标
- 不过这样做的时间复杂度达到了 O(N), 没有利用到给定数组是山脉数组的条件, 如何优化呢?
- 根据题目描述, 我们可以提取以下信息:
- 数组只有一个峰顶
- 峰顶下标的可能范围一定是
[1,n-2] - 相邻下标的值一定不相等
- 数组开头到峰顶单调递增, 峰顶到结尾单调递减
- 不难发现数组具有有序性, 我们可以利用二分查找来解决, 这样就能优化时间复杂度到 O(logN)了
- 具体做法如下:
- 首先初始化查找的上下界 s=1, e=n-2
- 然后取当前区间的中间下标 m, 并判断它和左右邻居的关系
- 如果它小于右邻居, 说明还在左边上坡, 向右继续查找峰顶
- 如果左邻居大于它, 说明已经到了右边下坡, 向左继续查找峰顶
- 否则说明它同时大于左右邻居 (相邻下标的值一定不相等), 就是要查找的峰顶, 返回其下标即可
- 下面代码中有详细的注释, 方便大家理解
复杂度
- 时间复杂度 O(logN): 二分查找每次都会将问题规模减半, 所以是 O(logN)
- 空间复杂度 O(1): 只使用了几个常数空间的变量
代码
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
# 利用给定数组是山脉数组的条件, 二分查找峰顶
# 这里使用1和len-2作为起点和终点, 因为数组开头和结尾肯定不是峰顶
# 这样做还有个好处: 比较相邻数字时无需判断下标, 因为它们一定不越界
s, e = 1, len(arr) - 2
while s <= e:
m = (s + e) >> 1
if arr[m] < arr[m + 1]:
# 当前m是在左边上坡, 向右继续查找峰顶
s = m + 1
elif arr[m - 1] > arr[m]:
# 当前m是在右边下坡, 向左继续查找峰顶
e = m - 1
else:
# 找到峰顶了, 返回对应下标
return m
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号