LeetCode 面试题 17.14. 最小K个数

2026-06-05 HGNULB 约 5 分钟

文章信息 12 个分类 5 个标签

分类

LeetCode CodeTop 中等未解决 20-50 程序员面试金典（第 6 版）腾讯字节美团百度网易快手

题目描述

✅ 面试题 17.14. 最小 K 个数

题意分析

从整数数组中找出最小的 k 个数。按出现位置计数，重复值可以占据多个名额，不能先去重；k 可以为零，此时返回空数组。

LeetCode 原题允许任意顺序返回，本页另一份题面要求升序。下面统一按升序输出，同时满足这两种要求：先选出最小的 k 个数，再利用堆的出队顺序组织结果，不必对整个输入排序。

解法：大小为 K 的最大堆

核心思路

[!blue]

只需保留最小的 k 个候选，不必知道其他元素之间的顺序。新元素到来时，最应该被淘汰的是候选中最大的那个，因此维护大小不超过 k 的最大堆，让堆顶始终是当前最差候选。

堆未满时直接加入。堆满后，如果新值不小于堆顶，当前已有 k 个不大于它的候选，丢弃它不会漏掉更小的数；如果新值小于堆顶，就淘汰堆顶、加入新值，得到更优的候选集合。

因此每处理完一个输入前缀，堆中都保存这个前缀最小的 min(k, 已处理数量) 个数。相等值也按各次出现分别加入；堆满后遇到与堆顶相等的新值，替换与否都不改变结果中的数值及数量，所以直接跳过。

为满足升序输出，扫描结束后依次弹出堆顶。最大堆每次给出剩余候选中的最大值，将它从结果数组的最后一格向前填写，最终数组就从小到大排列。这一步直接利用堆已有的顺序能力，无需再调用排序，也避免误把堆内部数组当成有序序列。

k == 0 必须在读取堆顶之前返回。Go 中通过 heap.Pop 获取最大值，它会先维护堆序，再调用类型的 Pop 方法移除末尾；不能直接调用底层 Pop 来代替堆操作。

解题步骤

k == 0 时返回空数组，否则创建最大堆。

扫描输入：堆不足 k 个元素时入堆，堆已满时只接纳小于堆顶的新值，并淘汰原堆顶。

创建长度为 k 的结果数组。

从结果末尾向前填写，每次弹出最大堆的堆顶。

返回已经升序排列的结果。

代码实现

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        for (int value : arr) {
            if (maxHeap.size() < k) {
                maxHeap.offer(value);
            } else if (value < maxHeap.peek()) {
                // 堆已满且新值更小时，只淘汰最大的候选。
                maxHeap.poll();
                maxHeap.offer(value);
            }
        }

        int[] answer = new int[k];
        for (int index = k - 1; index >= 0; index--) {
            answer[index] = maxHeap.poll();
        }

        return answer;
    }
}

import "container/heap"

type maxHeap []int

func (h maxHeap) Len() int { return len(h) }

func (h maxHeap) Less(i, j int) bool { return h[i] > h[j] }

func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *maxHeap) Push(value any) {
    *h = append(*h, value.(int))
}

func (h *maxHeap) Pop() any {
    old := *h
    last := old[len(old)-1]
    *h = old[:len(old)-1]
    return last
}

func smallestK(arr []int, k int) []int {
    if k == 0 {
        return []int{}
    }

    h := &maxHeap{}
    for _, value := range arr {
        if h.Len() < k {
            heap.Push(h, value)
        } else if value < (*h)[0] {
            // 堆已满且新值更小时，只淘汰最大的候选。
            heap.Pop(h)
            heap.Push(h, value)
        }
    }
    answer := make([]int, k)
    for index := k - 1; index >= 0; index-- {
        answer[index] = heap.Pop(h).(int)
    }
    return answer
}

复杂度分析

设数组长度为 $n$。

时间复杂度：$k>0$ 时为 $O(n\log(k+1))$。扫描维护堆需要 $O(n\log(k+1))$，依次弹出并填写结果需要 $O(k\log(k+1))$，因 $k\le n$ 而被前者覆盖；$k=0$ 时直接返回。

辅助空间复杂度：$O(k)$，保存候选堆；返回的结果另占 $O(k)$。

关键点总结

[!green]

求最小的若干个数时，用最大堆暴露最应淘汰的候选。

堆满后仅在新值更小时替换，保持前缀最小 k 个数的不变式。

最大值依次弹出并从答案末尾填写，直接得到升序结果，重复值照常保留。

易错点总结

[!yellow]

使用最小堆会把最好候选放在堆顶，无法直接淘汰候选中的最大值。

堆满后无条件替换，会让更大的新值挤掉本应保留的小值。

k == 0 不提前返回，会在第一次比较时读取空堆。

比较器用两个整数相减可能溢出，Java 使用 Comparator.reverseOrder() 表达反序。

不要先去重，题目选择的是 k 个出现位置上的值；堆内部遍历也不保证升序，升序版需要按堆顶逐次弹出。

最大堆出队是从大到小，写入结果时必须从末尾向前，不能从头开始。

相似题目

题目	难度	关联与区别
703. 数据流中的第 K 大元素	简单	原题持续加入数据并查询第k大，本题只做一次选择，可用快速选择或堆。
347. 前 K 个高频元素	中等	同样挑选TopK，原题排名依据为元素频次，本题依据数值大小。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/93040297

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！