[分析] 暴力法,按序扫描数组,找到peak element。提示说复杂度可以是logN级别的,那就要二分查找了,如何进行二分呢?考察nums[mid]和其左右相邻元素:若nums[mid] < nums[mid + 1], 则右侧必存在一个局部最大值,简略证明:若右侧一直是升序,则最后一个元素是peak element, 否则,第一次升序的波峰处是一个peak element。同理,若num[mid] < nums[mid - 1], 则左侧必存在一个局部最大值。若前面两种情况都不成立,则mid处就是一个局部最大值。
public class Solution {
public int findPeakElement1(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
if (nums.length == 1)
return 0;
int N = nums.length;
for (int i = 1; i < N - 1; i++) {
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
return i;
}
if (nums[0] > nums[1])
return 0;
else if (nums[N - 1] > nums[N - 2])
return N - 1;
else
return -1;
}
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
if (nums.length == 1 || nums[0] > nums[1])
return 0;
int N = nums.length;
int left = 0, right = N - 1;
while (right >= left) {
if (left == right)
return left;
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1])
left = mid + 1;
else if (nums[mid] < nums[mid - 1])
right = mid - 1;
else
return mid;
}
return -1;
}
}
分享到:
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode 答案解析 golang解答
leetcode中文版leetcode作弊 leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是...
vscode提交leetcode Leetcode刷题存档 准备 vscode 安装 leetcode 插件 添加leetcode到bin ln -s ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/...
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
leetcode 分类 简介: LeetCode-Viewer是一个利用Python爬取LeetCode-CN的做题信息,并通过Vuepress构建网页展示出来的一个项目,具体可以参考Demo: 下面给先看一下吧: 使用方式 fork该工程,然后clone到本地,...
leetcode 2 和 c leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。