原题
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[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。
解法
思想
- 线性查找，从第一个元素开始，第一个打破单调递增的元素。
- 二分查找，看中间元素值的的趋势（斜率）
代码
- 线性查找
class Solution {
public int findPeakElement(int[] nums) {
int n = 1;
int cache = nums[0];
while(n<nums.length &&nums[n]>=cache){
cache = nums[n];
n++;
}
return n-1;
}
}
- 二分查找（来源：leetcode官方）
public class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode162-%e5%af%bb%e6%89%be%e5%b3%b0%e5%80%bc/
相关推荐
-
leetcode21-合并两个有序链表
原题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入： 1->2->4, 1->3->4 输出： 1->1->2->3-...
-
leetcode485-最大连续1的个数
原题 给定一个二进制数组， 计算其中最大连续1的个数。 示例 1: 输入： [1,1,0,1,1,1] 输出： 3 解释： 开头的两位和最后的三位都是连续1，所以最大连续1的个数是...
-
leetcode173-二叉搜索树迭代器
原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例： BSTIterator iterator...
-
leetcode739-每日温度
原题 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 te...
-
leetcode611-有效三角形的个数
原题 给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入： [2,2,3,4] 输出： 3 解释： 有效的组合是: 2,3,4 (使用...
-
leetcode235-二叉搜索树的最近公共祖先
原题 给定一个二叉二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x ...
-
leetcode146-LRU缓存机制
原题 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 获取数据 get(key) -...
-
leetcode365-水壶问题
原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升...
-
leetcode837-新21点
原题 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下： 爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一...
-
leetcode238-除自身以外数组的乘积
原题 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积...
