LeetCode 补充题 110. 寻找数组的局部最小值
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 162. 寻找峰值
:::
给你一个非空整数数组
nums，相邻元素保证不相等。请返回任意一个严格小于左右相邻元素的元素下标。端点只需小于它在数组内唯一的相邻元素；如果数组只有一个元素，返回
0。你必须实现时间复杂度为
O(log n)的算法。
示例 1：
输入：
nums = [5,2,3]
输出：1
解释： 下标 1 的值 2 严格小于两侧的 5、3。
示例 2：
输入：
nums = [1,2,3]
输出：0
解释： 左端点 1 小于右邻居 2，满足局部最小定义。
提示：
- 相邻元素保证不相等。
- 单元素数组返回
0。
题意分析
目标是任意局部最小值，不要求整个数组的最小值。虽然数组无序，但相邻元素不等，使得每次比较都能确定一个严格下降方向。沿下降方向走到转折处或端点，一定能找到局部最小值。
解法：沿下降方向二分找谷值
核心思路
[!blue]
将数组外侧视为正无穷，维护闭区间
[left,right]，使其左边界小于外侧左邻居、右边界小于外侧右邻居。这个区间内至少有一个谷值。若
a[mid] > a[mid + 1]，令left = mid + 1，新左边界严格小于被舍弃的左邻居，右边界条件不变。否则相邻不等保证a[mid] < a[mid + 1]，令right = mid，同样保留边界条件。当两边界重合，这个元素同时小于两侧邻居，就是所求谷值。循环中
left < right保证mid < right，因此访问mid + 1不越界；单元素数组无需进入循环。
解题步骤
- 初始化闭区间为整个非空数组。
- 中点大于右邻居时保留右半，否则保留左半和中点。
- 两端相遇后返回该位置。
代码实现
class Solution {
public int localMinimum(int[] a) {
int left = 0;
int right = a.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (a[mid] > a[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
func localMinimum(a []int) int {
left, right := 0, len(a)-1
for left < right {
mid := left + (right-left)/2
if a[mid] > a[mid+1] {
left = mid + 1
} else {
right = mid
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
保留的区间始终包含一个谷值：沿下降方向走，不可能一直下降而没有在内部或边界形成局部最小。
易错点总结
[!yellow]
这里明确要求相邻不等；存在相等平台时，严格谷值可能不存在，不能直接沿用该保证。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 162. 寻找峰值 | 中等 | 把寻找峰值的比较方向反转即可找谷值，两题都依赖相邻值不等和边界约定。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！