题目重点:Uber OA 四题之一要求找出严格高于左右相邻数的元素并求和;两端只比较唯一邻居。给线性扫描、相等值与单元素边界说明。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 长度至少 2 时,内部元素必须严格大于左右两个邻居;首尾只需严格大于唯一邻居。所有满足条件的元素数值相加,允许负整数。
- 空数组返回 0;单元素数组没有邻居,本文按‘对所有现有邻居都严格大于’的空集真值把它计入总和。若在线判题把单元素特殊设为 0,需按官方约定调整。
- 相等不算峰值,例如 [2,2] 两端都不计。
解题路线
- 线性遍历每个下标 i,仅在存在左邻时检查 values[i]>values[i−1],存在右邻时检查 values[i]>values[i+1]。
- 任意一个已存在邻居不小于当前值,当前项就不计;两个条件都通过时把当前值加入总和。
- 每个位置的局部性质与其他峰值是否选中无关,因此逐项判断后求和即为完整答案。
手动走一遍
[2,5,1,4,4,0] 中 5 严格高于 2 和 1;两个 4 相邻相等,都不是峰值;末尾 0 低于左邻。总和为 5。[-3,-5] 中首项 -3 高于 -5,和为 -3,不能把结果默认截为 0。
Python 参考实现
下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。
代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。
"""Sum elements strictly greater than every existing adjacent element."""
def sum_local_peaks(values: list[int]) -> int:
total = 0
for i, value in enumerate(values):
if i > 0 and value <= values[i - 1]:
continue
if i + 1 < len(values) and value <= values[i + 1]:
continue
total += value
return total
复杂度
逐元素至多比较两次,时间 O(n),除求和变量外 O(1) 额外空间。若输入流只允许单遍且不能回看,可保留前两项,在读到下一项时决定中间项。
易错点与追问
容易失分的边界
- 把比较写成 ≥ 会把平台期错误计入峰值。
- 首尾不能访问不存在的第二邻居;单元素行为题目未定义,需明确约定。
- 数组可含负数,峰值求和也可为负,不能把 0 当成下界。
继续深挖
- 若要求返回峰值下标而非数值和,判断条件不变,改为收集 i。
- 若峰值定义扩大到距离 d 内所有元素,直接检查每项左右 d 个值需 O(nd),可讨论滑动窗口最大值与相等值处理。
