您现在的位置是：首页 > Python

当前栏目

[Leetcode][python]寻找峰值

2023-03-02 11:11:57 时间

## 题目大意 ##

[https://leetcode-cn.com/problems/find-peak-element/description/][https_leetcode-cn.com_problems_find-peak-element_description]

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums\[i\] ≠ nums\[i+1\]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums\[-1\] = nums\[n\] = -∞。

## 解题思路 ##

二分查找变种

## 代码 ##

### 方法1：顺序遍历。 ###

本题的一个重要特点是，从第一个元素开始，若其大于相邻的后续元素，则第一个元素就是一个局部最大值，返回即可。若其小于相邻的后续元素，则第二个元素大于第一个元素。如此，一一遍历数组，第一次出现，第i个元素若大于其相邻后续元素，则该元素就是一个局部最大值

### 方法2：二分查找 ###

思路：如果中间元素大于其相邻后续元素，则中间元素左侧(包含该中间元素）必包含一个局部最大值。如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。

class Solution(object):
        def findPeakElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            left = 0
            right = len(nums)-1
            while left <= right:
                print left, right
                if left == right:
                    return left
                mid = left + (right -left) / 2 
                # 如果中间小于右边，那么一定在右边
                if nums[mid] < nums[mid+1]:
                    left = mid + 1
                # 左边不小于右边，那么直接把右边弄到中间
                else:
                    # right不可以是mid-1，万一正好是mid，就跳过了，因为并没有比对mid的值
                    right = mid

## 总结 ##

[https_leetcode-cn.com_problems_find-peak-element_description]: https://leetcode-cn.com/problems/find-peak-element/description/

猜你喜欢

「  给typecho评论添加数字验证码  」
「  typecho主题设置pjax无刷新加载  」
「  记录一次修改yunzai示例插件达到查询学校寝室电量的目的  」
「  Centos安装go环境教程  」
「  关于本站图床，我有话说...  」
js map函数的用法
「  TYPECHO主题-NoLine  」
个人图床的搭建 - wuuconix's blog
react子父组件互相通信传值
vscode+react环境部署，运行第一个react框架
一个初级前端结合css、div谈一谈屏幕尺寸、分辨率、缩放概念
C语言学习第二章安装编译器及运行环境
一个前端开发对于Flex布局的总结（图解，简单易懂，全）
使用git命令与vscode从零开始对远程代码仓库进行拉取、提交、合并、推送分支等操作在项目中的实践
MacOS Monterey12.1-12.3版本连接L2TP无法正常访问公司内网非完美解决方案（详细）
制作一个炫酷的github个人主页
L1 赛道终局未定，抗量子隐私公链会成下一个热点吗？
Yate for Mac(音乐标签管理工具) 6.13中文版
功能最全、使用简单的PDF阅读及编辑软件2021版！PDF编辑器全版本下载
用起来爱不释手的PDF阅读编辑软件，含OCR功能：PDF-Xchange editor 9.0

zl程序教程

当前栏目

[Leetcode][python]寻找峰值

相关文章