题目重点:OA 第一题找首个内部元素,左右邻居均严格大于它;返回值/下标与端点规则在题目未保存。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练版返回首个满足 a[i−1]>a[i] 且 a[i+1]>a[i] 的 0-based 下标 i;若原题要求值,最后返回 a[i] 即可。
- 只有 1≤i≤n−2 的内部元素有两个相邻邻居;长度<3 或无匹配返回 -1。
- 严格比较,相等不算;输入元素可为负数/重复值。
解题路线
- 从 i=1 到 n−2 顺序遍历,用两个独立严格 > 判断。
- 第一个成立的 i 立即返回,因扫描顺序即 first 的定义;否则返回 -1。
- 问清返回格式后,只把最终 i 映射为元素值/下标,不改变判定。
- 测 [4,1,3] 命中中间、[4,4,3] 不命中、多个谷底取首个、空/短数组和负数。
手动走一遍
训练 [5,2,4,1,3]:i=1 的 2 两侧 5/4 均大于它,故先返回下标 1;尽管 i=3 的 1 也满足,不能跳到更小数值。
规模与取舍
n 个元素最坏扫描 n−2 次,O(n) 时间、O(1) 空间。
易错点与追问
容易失分的边界
- 找全局最小值而非第一个局部低点。
- 允许端点只比较一个邻居。
- 用 ≥ 而非严格 >,重复值误中。
- 未确认就把输出下标当题目规定。
继续深挖
- 若要求所有局部低点?
- 数组可随机访问且保证存在局部低点时能否二分?
- 环形数组的端点邻居如何定义?
