寻找锯齿折线图中右侧仅含一段折线的峰值点高效算法

问题定义与前提 #

给定锯齿折线图（所有中间点非峰即谷：对任意中间点i，要么y[i] > y[i-1]且y[i] > y[i+1]（峰值），要么y[i] < y[i-1]且y[i] < y[i+1]（谷值），无连续上升/下降段），需找出所有右侧仅包含一段折线的峰值点——即该峰值点是其右侧所有点的全局最高点，右侧折线不会被更高的峰值截断（对应示例中的蓝色线段左端点）。

最优算法思路 #

避免逐一校验每个峰值右侧所有点的低效方式，我们采用两次线性遍历的O(n)复杂度算法：

1. 标记所有峰值点：遍历一次折线点，标记出所有符合峰值定义的点。
2. 从右往左筛选目标峰值：维护当前遍历到的最高y值，从右往左检查每个峰值点：
   • 若当前峰值的y值大于已记录的右侧最高值，说明该峰值是右侧所有点的最高点，符合要求。
   • 更新当前最高值为该峰值的y值，继续向左遍历。

Python 实现示例 #

def find_target_peaks(points):
    n = len(points)
    if n < 3:
        return []
    
    # 第一步：标记所有峰值点
    is_peak = [False] * n
    for i in range(1, n-1):
        prev_y = points[i-1][1]
        curr_y = points[i][1]
        next_y = points[i+1][1]
        if curr_y > prev_y and curr_y > next_y:
            is_peak[i] = True
    
    # 第二步：从右往左筛选目标峰值
    target_peaks = []
    current_max_y = -float('inf')
    # 从倒数第二个点向左遍历（最后一个点不可能是峰值）
    for i in range(n-2, 0, -1):
        if is_peak[i]:
            curr_y = points[i][1]
            if curr_y > current_max_y:
                target_peaks.append(points[i])
                current_max_y = curr_y
    
    # 反转恢复x递增顺序
    return target_peaks[::-1]

R 实现示例（适配用户提供的示例数据） #

find_target_peaks <- function(df) {
  n <- nrow(df)
  if (n < 3) return(data.frame())
  
  # 标记所有峰值点
  df$is_peak <- FALSE
  for (i in 2:(n-1)) {
    prev_y <- df$y[i-1]
    curr_y <- df$y[i]
    next_y <- df$y[i+1]
    if (curr_y > prev_y && curr_y > next_y) {
      df$is_peak[i] <- TRUE
    }
  }
  
  # 从右往左筛选目标峰值
  target_peaks <- list()
  current_max_y <- -Inf
  for (i in (n-1):2) {
    if (df$is_peak[i]) {
      curr_y <- df$y[i]
      if (curr_y > current_max_y) {
        target_peaks[[length(target_peaks)+1]] <- df[i, ]
        current_max_y <- curr_y
      }
    }
  }
  
  # 反转恢复x递增顺序
  target_peaks <- do.call(rbind, rev(target_peaks))
  return(target_peaks)
}

# 测试示例数据
f <- read.table(pipe('curl -s https://i.sstatic.net/tMB1y.gif | tail -c +43 | zcat'), header=T, sep='\t')
targets <- find_target_peaks(f)
# 绘图验证（与示例效果一致）
with(f, plot(x, y, type='l'))
invisible(apply(targets, 1, function(v) { segments(v[['x']], v[['y']], 1e6, v[['y']], col='blue') }))

算法优势 #

• 时间复杂度O(n)：仅需两次线性遍历，远优于逐个校验峰值右侧所有点的O(n²)算法。
• 空间复杂度O(n)：仅需存储峰值标记和结果列表，内存占用低。

内容的提问来源于stack exchange，提问作者user1424739