Find Peak or Valley

2/28/2026 tech

给定一个整数数组 A，长度为 n

  1. 数组相邻元素之间的差的绝对值为 1: abs(A[i] - A[i+1]) = 1
  2. 数组仅有一个波峰或波谷

问题：请快速反回这个波峰或波谷的位置

# Solutions

# O(log⁡n)O(\log n) time

def findPeakValley(A):
  n = len(A)
  # binary search: A[i] < A[i+1]?
  # yes, mid = i+1
  # no, mid = i-1
  # find peak first
  lo, hi = 0, n-2
  while lo <= hi:
    mid = (lo + hi) // 2
    if A[mid] < A[mid+1]:
      lo = mid+1
    else: # A[mid] > A[mid+1]:
      hi = mid-1
  if A[mid] > A[mid-1] and A[mid] > A[mid+1]:
    return mid
  
  # now find valley
  lo, hi = 0, n-2
  while lo <= hi:
    mid = (lo + hi) // 2
    if A[mid] < A[mid+1]:
      hi = mid-1
    else: # A[mid] > A[mid+1]:
      lo = mid+1
  return mid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# O(1)O(1) time

TODO: use math