162.寻找峰值(Medium)
# 题目描述
查找数据中峰值元素,峰值元素是值大于左右相邻值的元素。返回元素的位置
# 样例
Input: [1,2,3,1]
Output: 2
# 3是峰值元素,返回其索引 2
1
2
3
2
3
# 题目解析
# 方法一:线性扫描
遍历数组元素,查找值是大于左右相邻元素
线性扫描的时间复杂度是 $O(n)$,空间复杂度是 $O(1)$
# 方法二:二分搜索
粗看本题不满足二分查找的有序条件。二分查找是通过左右指针逼近的方式查找 峰值
。
将中间值与右元素进行比较
- 当中间值大于右元素,满足单调减:right = mid
- 当中间值小于等于右元素,递增,肯定不满足条件: left = mid + 1
# Python代码示例
线性扫描
线性扫描有两种实现方式
对边界特殊处理
利用单调性处理:
默认数组是单调递增,一旦出现右边的值小的话,就找到索引。对于最后一个元素单独处理。
# 边界处理
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
for i in range(len(nums)):
if (i == len(nums) - 1 or nums[i] > nums[i+1]) and \
(i == 0 or nums[i] > nums[i-1]):
return i
return len(nums) - 1
# 单调性写法
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i
return len(nums) - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
二分查找1:找到 mid > 右 最靠右的值
# 模板2 二分查找 mid > 右 最靠右的值
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) >> 1
if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1
return left
# 模板1 二分查找, 使用ans记录
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
ans = 0
while left <= right:
mid = (left + right) >> 1
if mid == len(nums) - 1 or nums[mid] > nums[mid + 1]: # 这里可能取最右值
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
二分查找2:找到 左 < mid 最靠左的值
# 模板2 找到 左 < mid 最靠左的值
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums)
while left < right:
mid = (left + right) >> 1
if mid == 0 or nums[mid] > nums[mid - 1]:
left = mid + 1
else:
right = mid
return left - 1
# 模板1
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
ans = 0
while left <= right:
mid = (left + right) >> 1
if mid == 0 or nums[mid] > nums[mid - 1]:
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54