使用Racket编写peaks函数筛选列表峰值元素的问题咨询

问题原因 #

1. 代码存在语法缺失 #

你贴出的代码片段中，缺失了求最大值辅助函数的定义头(define (greatest lon)，如果实际运行的代码也漏写了这部分，会直接触发函数未定义的报错，导致无法得到预期结果。

2. 实现性能严重冗余 #

补全语法后你的逻辑实际可以跑出正确结果，但时间复杂度为O(n²)：每次递归调用peaks时，都要重新遍历当前子列表计算最大值，长列表下运行效率会非常低。 #

优化实现方案 #

用递归特性从右往左处理列表，只需一次遍历即可得到结果，时间复杂度为O(n)，更适合递归学习场景理解：

; 补全后的求列表最大值辅助函数（如果继续用原有逻辑可以保留，优化方案不需要额外辅助函数）
(define (greatest lon)
  (cond
    [(empty? (rest lon)) (first lon)]
    [else (max (first lon) (greatest (rest lon)))]))

; 优化后的peaks函数，无需额外辅助函数
(define (peaks lon)
  (cond
    [(empty? lon) empty]
    [(empty? (rest lon)) lon]
    [else
     (let ([rest-peaks (peaks (rest lon))])
       (if (> (first lon) (first rest-peaks))
           (cons (first lon) rest-peaks)
           rest-peaks))]))

测试验证 #

运行你给出的示例：
(peaks (cons 1 (cons 6 (cons 4 (cons 5 empty)))))
输出结果为(cons 6 (cons 5 empty))，完全符合要求。

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