【Leetcode刷题Python】162. 寻找峰值
2023-09-14 09:12:59 时间
1 题目
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1:
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
示例 2:
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
2 解析
有序数组,时间复杂度为 O(log n) 的算法,立马想到二分查找法。
数组的一半,一定是有序的,只要求出其中有序部分的最大值即可。比如【7,8,9,1,2,3,4,5】的右边一半【2,3,4,5】,只要找出这部分的最大值就是正确的。再比如【6,7,8,9,1,2,3】的左边一半【6,7,8,9】,找出此部分的最大值就是正确的。
3 Python实现
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left,right = 0,len(nums)-1
while left <right:
mid = (left+right)//2
if nums[mid] <nums[mid+1]:
left = mid+1
else:
right = mid
return left
相关文章
- Python 刷Leetcode题库,顺带学英语单词(31)
- Python之ffmpeg-python:ffmpeg-python库的简介、安装、使用方法之详细攻略
- Python编程语言学习:python编程语言中重要函数讲解之map函数等简介、使用方法之详细攻略
- Python:python语言中与时间有关的库函数简介、安装、使用方法(获取当前时间/计算程序块前后运行时间/模型训练时间或耗费时间)之详细攻略
- Python编程语言学习:python中与数字相关的函数(取整等)、案例应用之详细攻略
- Python语言学习之文件格式后缀那些事:python和常见各种文件格式后缀介绍、使用方法之详细攻略
- Python之ffmpeg-python:ffmpeg-python库的简介、安装、使用方法之详细攻略
- 【LeetCode Python实现】13. 罗马数字转整数(简单)
- 【Leetcode刷题Python】 860.柠檬水找零
- 【Leetcode刷题Python】142.环形链表II
- 【Leetcode刷题Python】145. 二叉树的后序遍历
- 【Leetcode刷题Python】94. 二叉树的中序遍历
- 【Leetcode刷题Python】131. 分割回文串
- 【Leetcode刷题Python】216. 组合总和 III
- 【Leetcode刷题Python】22. 括号生成
- 【Leetcode刷题Python】367. 有效的完全平方数
- 【Leetcode刷题Python】278. 第一个错误的版本
- 【Leetcode刷题Python】611. 有效三角形的个数
- 【Leetcode刷题Python】矿泉水问题
- 【Leetcode刷题Python】518. 零钱兑换 II
- 【Leetcode刷题Python】322. 零钱兑换
- 【Leetcode刷题Python】53. 最大子数组和
- 【Leetcode刷题Python】剑指 Offer II 082. 含有重复元素集合的组合
- 【Leetcode刷题Python】生词本单词整理
- 【Leetcode刷题Python】257. 二叉树的所有路径
- 【Leetcode刷题Python】104. 二叉树的最大深度
- 【Leetcode刷题Python】297. 二叉树的序列化与反序列化
- 【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
- 【Leetcode刷题Python】337. 打家劫舍 III