知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 06 - 寻找峰值 ## 题目(LeetCode 162) 给定一个数组,找到任意一个**峰值**的下标。峰值 = 大于左右邻居的元素。 ``` 输入:nums = [1, 2, 3, 1] 输出:2(nums[2] = 3 是峰值,3 > 2 且 3 > 1) 输入:nums = [1, 2, 1, 3, 5, 6, 4] 输出:1 或 5(nums[1]=2 > 1 且 > 1,nums[5]=6 > 5 且 > 4) 输入:nums = [1, 2, 3] 输出:2(边界只有一边邻居,只看一侧) ``` 条件: - `nums[-1] = nums[n] = -∞`(边界之外视为负无穷) - 相邻元素不相等 - 要求 O(log n) 时间 ## 大白话理解 虽然数组是无序的,但如果一个元素比它右边的元素小,说明右边在上坡,峰值一定在右边。 ``` 想象你在爬山: - 当前位置比下一步低 → 你在上坡 → 继续往高处走 - 当前位置比下一步高 → 你在下坡 → 回头往高处走 - 一直往高处走,就一定能走到山顶(峰值) ``` ``` ● ← 峰值 / \ / \ / ● / / ● / / ● ``` 只要每次朝着**更高的方向**走,就一定能到达峰值。因为边界外是 -∞,所以越往高走越不可能"卡住"。 ## 关键洞察:比较 nums[mid] 和 nums[mid+1] ``` 如果 nums[mid] < nums[mid+1]: → mid 在上升坡上,峰值在 mid 右边(含 mid+1) → l = mid + 1 如果 nums[mid] > nums[mid+1]: → mid 在下降坡上,峰值在 mid 左边(含 mid) → r = mid ``` ``` 为什么一定能在高的一边找到峰值? 案例1:nums[mid] < nums[mid+1],右边一直递增 mid mid+1 n ┌────┬────┬────┬────┬────┬────┐ │ 2 │ 5 │ 7 │ 8 │ 10 │ 12 │ └────┴────┴────┴────┴────┴────┘ ↑ 最右边是峰值(右侧是 -∞) 案例2:nums[mid] < nums[mid+1],右边先升后降 mid mid+1 ┌────┬────┬────┬────┬────┬────┐ │ 2 │ 5 │ 8 │ 7 │ 4 │ 1 │ └────┴────┴────┴────┴────┴────┘ ↑ 最高点就是峰值 无论如何,往高处走总能碰到峰值! ``` ## 代码 ```java public int findPeakElement(int[] nums) { int l = 0, r = nums.length - 1; while (l < r) { // 注意:l < r,不是 l <= r int mid = l + (r - l) / 2; if (nums[mid] < nums[mid + 1]) { // 在上升坡 → 峰值在右边 l = mid + 1; } else { // 在下降坡 → 峰值可能是 mid 或在左边 r = mid; // 不能 mid-1,mid 可能就是峰值 } } // 退出时 l == r,指向峰值 return l; } ``` > 💬 **Q:为什么用 `while(l < r)`?** > > 和旋转数组找最小值同样的原因:缩小边界用了 `r = mid`(不跳过 mid),如果写 `while(l <= r)`,当 `l == r` 时 `r = mid` 不变,会死循环。 > > 当 `l == r` 时说明区间缩小到一个元素,它就是峰值。 ## 过程模拟 ### 场景1:标准案例 ``` nums = [1, 2, 3, 1] 索引: 0 1 2 3 第1轮: l=0, r=3, mid=1 nums[1]=2 < nums[2]=3 → 上升坡 → l = mid+1 = 2 [1, 2, 3, 1] ↑ ↑ mid mid+1 └→ 上升,往右走 第2轮: l=2, r=3, mid=2 nums[2]=3 > nums[3]=1 → 下降坡 → r = mid = 2 [1, 2, 3, 1] ↑ 下降 第3轮: l=2, r=2 → l < r 不成立,退出 nums[2] = 3 → 峰值 ✓ (3 > 2 且 3 > 1) ``` ### 场景2:多个峰值 ``` nums = [1, 2, 1, 3, 5, 6, 4] 索引: 0 1 2 3 4 5 6 第1轮: l=0, r=6, mid=3 nums[3]=3 < nums[4]=5 → 上升坡 → l=4 第2轮: l=4, r=6, mid=5 nums[5]=6 > nums[6]=4 → 下降坡 → r=5 第3轮: l=4, r=5, mid=4 nums[4]=5 < nums[5]=6 → 上升坡 → l=5 第4轮: l=5, r=5 → 退出 nums[5] = 6 → 峰值(答案之一)✓ 注意:1 也是峰值(下标 1),但二分不会走到那里 因为一直往高处走,自然会走到最高的峰值 ``` ### 场景3:单调递增 ``` nums = [1, 2, 3, 4, 5] 第1轮: l=0, r=4, mid=2 nums[2]=3 < nums[3]=4 → 上升 → l=3 第2轮: l=3, r=4, mid=3 nums[3]=4 < nums[4]=5 → 上升 → l=4 第3轮: l=4, r=4 → 退出 nums[4] = 5 → 峰值 ✓ (5 > 4 且右边是 -∞,满足条件) ``` ### 场景4:单调递减 ``` nums = [5, 4, 3, 2, 1] 第1轮: l=0, r=4, mid=2 nums[2]=3 > nums[3]=2 → 下降 → r=2 第2轮: l=0, r=2, mid=1 nums[1]=4 > nums[2]=3 → 下降 → r=1 第3轮: l=0, r=1, mid=0 nums[0]=5 > nums[1]=4 → 下降 → r=0 第4轮: l=0, r=0 → 退出 nums[0] = 5 → 峰值 ✓ (5 左边是 -∞ 右边是 4,满足条件) ``` ## 复杂度 - 时间:O(log n) - 空间:O(1) ## 为什么 O(log n) 能用于无序数组? 虽然整体无序,但二分在这里不是靠全局有序,而是靠**局部单调性**: ``` 关键性质: "如果 nums[mid] < nums[mid+1],峰值一定在右边" "如果 nums[mid] > nums[mid+1],峰值一定在左边" 这是由边界条件(-∞)保证的: 如果你一直往右走(上坡),最终会遇到一个下坡(因为最右是 -∞) 上坡和下坡的交界处,就是峰值 ``` ## 一句话总结 比较 `nums[mid]` 和 `nums[mid+1]`:上坡往右走,下坡往左走,一直朝高处爬就能找到峰值。 --- 上一篇:[05 - 搜索插入位置](./05-search-insert.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入