SWE · CodeSignal OA

Capital One 首个严格局部低点:两侧邻居都更大

OA 第一题找首个内部元素,左右邻居均严格大于它;返回值/下标与端点规则在题目未保存。

题目重点:OA 第一题找首个内部元素,左右邻居均严格大于它;返回值/下标与端点规则在题目未保存。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练版返回首个满足 a[i−1]>a[i] 且 a[i+1]>a[i] 的 0-based 下标 i;若原题要求值,最后返回 a[i] 即可。
  • 只有 1≤i≤n−2 的内部元素有两个相邻邻居;长度<3 或无匹配返回 -1。
  • 严格比较,相等不算;输入元素可为负数/重复值。

解题路线

  1. 从 i=1 到 n−2 顺序遍历,用两个独立严格 > 判断。
  2. 第一个成立的 i 立即返回,因扫描顺序即 first 的定义;否则返回 -1。
  3. 问清返回格式后,只把最终 i 映射为元素值/下标,不改变判定。
  4. 测 [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) 空间。

易错点与追问

容易失分的边界

  • 找全局最小值而非第一个局部低点。
  • 允许端点只比较一个邻居。
  • 用 ≥ 而非严格 >,重复值误中。
  • 未确认就把输出下标当题目规定。

继续深挖

  • 若要求所有局部低点?
  • 数组可随机访问且保证存在局部低点时能否二分?
  • 环形数组的端点邻居如何定义?
✓已复制微信号!