Найти три максимальных элемента числового списка за время O(n), где n-длина списка

(defun 3max (lst &optional (m1 (car lst)) (m2 (car lst)) (m3 (car lst)))
  (cond ((null lst) (list m1 m2 m3))
        ((> (car lst) m1) (3max (cdr lst) (car lst) m1 m2))
        ((> (car lst) m2) (3max (cdr lst) m1 (car lst) m2))
        ((> (car lst) m3) (3max (cdr lst) m1 m2 (car lst)))
        (t (3max (cdr lst) m1 m2 m3))))
 
==> 3max
 
(3max '(1 2 3 4 1 2 6 3))
 
==> (6 4 3)

(defun 3max (xs &aux (x (car xs)))
  (let ((a x) (b x) (c x))
    (dolist (x (cdr xs))
      (cond ((> x a) (setf c b b a a x))
            ((> x b) (setf c b b x))
            ((> x c) (setf c x))))
    (values a b c)))
 
(3max '(1 2 3 4 1 2 6 3))
; 6
; 4
; 3

;;; лямбда-стайл
(defun 3max (lst)
  ((lambda (f-rec) (f-rec lst '()))
    (lambda (lst acc)
      (if (cddr acc)
    (reverse acc)
    ((lambda (m) (f-rec (vl-remove m lst) (cons m acc)))
      (apply 'max lst))))))
 
;;; г*вн*стайл
(defun 3max (lst)
  (setq m (apply 'max lst) acc (list m))
  (repeat 2
    (setq
      lst (vl-remove m lst)
      m   (apply 'max lst)
      acc (cons m acc)))
  (reverse acc))

(use-package "TRACK-BEST")
 
(defun foo (xs &optional (keep 3))
  (with-track-best (:keep keep)
    (dolist (x xs)
      (track x x))))

(defun 3max (lst &optional (m1 (car lst)) (m2 (car lst)) (m3 (car lst)))
  (let ((ca (car lst)) (cd (cdr lst))
    (cond ((null lst) (list m1 m2 m3))
             ((> ca m1) (3max cd ca m1 m2))
             ((> ca m2) (3max cd m1 ca m2))
             ((> ca m3) (3max cd m1 m2 ca))
             (t (3max cd m1 m2 m3)))))

(defun 3max (lst)
  ((lambda (x) (list (car x) (cadr x) (caddr x)))
    (vl-sort lst '>)))

(defun f (xs)
  (destructuring-bind (%1 %2 %3 &rest xs) xs
    (reduce #'(lambda (xs x &aux (xs (cons x xs)))
                (remove (reduce #'min xs) xs))
            xs
            :initial-value (list %1 %2 %3))))

(defun f (xs &optional (n 1))
  (let ((init (subseq xs 0 n))
        (rest (nthcdr n xs)))
    (reduce #'(lambda (xs x &aux (xs (cons x xs)))
                (remove (reduce #'min xs)
                        xs))
            rest
            :initial-value init)))

CL-USER 1 > (defun f (xs &optional (n 1))
  (let ((init (subseq xs 0 n))
        (rest (nthcdr n xs)))
    (reduce #'(lambda (xs x &aux (xs (cons x xs)))
                (remove (reduce #'min xs)
                        xs))
            rest
            :initial-value init)))
F
 
CL-USER 2 > (f '(9 4 2 1 4 2 5) 3)
 
(5 9)

(defun get-n-max (lst n)
 (if (zerop n) 
     nil 
     (let ((max (apply 'max lst)))
        (cons max (get-n-max (removef max lst) (- n 1)))))) 
 
==> get-n-max
 
(get-n-max '(1 2 3 4 5 1 2 3 4 5 11 22 0 9) 4)
 
==> (22 11 9 5)
 
(get-n-max '(1 2 3 4 5 1 2 3 4 5 11 22 0 9) 5)
 
==> (22 11 9 5 5)

(defun f (xs &optional (n 1))
  (let ((init (subseq xs 0 n))
        (rest (nthcdr n xs)))
    (reduce #'(lambda (xs x &aux (xs (cons x xs)))
                (remove (reduce #'min xs)
                        xs
                        :count 1))
            rest
            :initial-value init)))