🗒️162. 寻找峰值
2024-5-22
| 2024-5-23
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
162. 寻找峰值 - 力扣（LeetCode）
162. 寻找峰值 - 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 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。   提示： * 1 <= nums.length <= 1000 * -231 <= nums[i] <= 231 - 1 * 对于所有有效的 i 都有 nums[i] != nums[i + 1]
162. 寻找峰值 - 力扣（LeetCode）
https://leetcode.cn/problems/find-peak-element
162. 寻找峰值 - 力扣（LeetCode）
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
示例 2：
提示：
  • 1 <= nums.length <= 1000
  • 231 <= nums[i] <= 231 - 1
  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]

按条件遍历一遍

二分查找

162. 寻找峰值 - 力扣（LeetCode）
162. 寻找峰值 - 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 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。   提示： * 1 <= nums.length <= 1000 * -231 <= nums[i] <= 231 - 1 * 对于所有有效的 i 都有 nums[i] != nums[i + 1]
162. 寻找峰值 - 力扣（LeetCode）
https://leetcode.cn/problems/find-peak-element/solutions/1987497/by-endlesscheng-9ass/
162. 寻找峰值 - 力扣（LeetCode）
二分查找 红蓝染色法_哔哩哔哩_bilibili
【学习提醒】建议先完成本节的课后作业，再开始下一节的学习！加油！34. 在排序数组中查找元素的第一个和最后一个位置 https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-t9l9/课后, 视频播放量 105993、弹幕量 153、点赞数 2285、投硬币枚数 1912、收藏人数 1764、转发人数 310, 视频作者 灵茶山艾府, 作者简介 算法讲师 | 力扣竞赛 Top10 | 全网刷题量 8000+，相关视频：Snippet4: 二分查找的唯一推荐写法，二分查找为什么总是写错？，数位 DP 通用模板，盛最多水的容器 接雨水，一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵），看到递归就晕？带你理解递归的本质！，2-2: 二分查找 Binary Search，二分查找模板的记忆方法，A05 二分查找算法 最好的板子，【递归2】如何治疗晕递归?
https://www.bilibili.com/video/BV1AP41137w7/
二分查找 红蓝染色法_哔哩哔哩_bilibili
为什么这个算法是可以的？
这个有点像高中学的二分法找函数的零点, 对于一个区间 , 可以先计算得到它的中点 (其中 是向下取整操作)。
  1. 如果满足 , 就往右边爬升（之所以对比 和它的右邻居, 是因为 是通过向下取整计算得到的, 在 的情况下肯定会存在右邻居)。
  1. 否则说明 ， 有可能就是峰值, 记录一下位置, 然后往左搜索检查它是不是真的是峰值。
闭区间是，对应的开区间就是
💡
为什么不考虑n-1呢？因为 n-1 的右边是负无穷，一定是满足的 nums[mid] > nums[mid + 1]

📎 参考

相关文章 :
算法题
  • Important
    • 118. 杨辉三角386. 字典序排数
    Loading...
    目录