本文概览：本文讲解数组中的第K个最大元素的核心思路：维护大小为 k 的最小堆，动态保留前 k 大的元素，堆顶即答案，时间复杂度 O(n log k)

一、题目

image-20260905003000001

二、题目分析

1. 题目要求

给定一个整数数组 nums 和一个整数 k，返回数组中第 k 个最大的元素。

注意：这题和"找最大值"的区别在于，需要知道是第几个最大的，而且相同的值也算一个位置。

例子：nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]，k = 4

1
2
3
4
5
6  5  5  4  3  3  2  2  1        ← 降序排序后
↑  ↑  ↑  ↑
1  2  3  4                      ← 排名（两个 5 各占第 2、3 名）
         ↑
      k=4 → 第 4 大 = 4

注意两个 5 占了第 2、第 3 两个位置，相同的值各算一个位置，所以第 4 大是 4，不是 3。

2. 暴力思路：排序

找最大值一般是排序（归并排序、快速排序），让数组有序后直接取。这题也可以用一样的思路：整体排序后取第 k 个。

问题：两个排序书写都比较麻烦，而且整体排序是 O(n log n)，但我们只需要"前 k 个最大的"，排后面的部分完全浪费了。

3. 更简单的思路：维护 k 大小的列表

我们要找第 k 大的元素，那换个角度想——如果手里始终留着"最大的前 k 个元素"，那这 k 个元素里最小的那个，不就是第 k 大吗？

基于这个想法，维护一个大小为 k 的列表：

  • 按顺序遍历数组，前 k 个元素直接填进列表

  • 列表满了之后，每来一个新元素，和列表里的最小值比较

    • 新元素 > 最小值 → 说明当前列表并不是真正的"前 k 大"，替换掉最小值

    • 新元素 ≤ 最小值 → 直接丢弃

  • 遍历结束，列表的最小值就是第 k 大

4. 这个方案的问题

列表的值动态变换，每次都要找列表的最小值来比较；而且替换掉最小值之后，新的最小值是谁又得重新找。

如果用普通列表，每次找最小值都要扫一遍 k 个元素，时间复杂度 O(n × k)。当 k 很大时，这比排序还慢。

优化方向：需要一种结构，能快速拿到最小值，且替换最小值之后还能快速维护新的最小值——这就是最小堆。

三、思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findKthLargest(int[] nums, int k) {
    // 最小堆
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        // 堆还没填满 k 个，直接加入
        if (minHeap.size() < k) {
            minHeap.offer(num);
        } else {
            // 新元素比堆顶（当前最小值）大，替换
            if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }
    }
    // 堆顶就是第 k 大
    return minHeap.peek();
}

思路简要说明：

  1. 维护大小为 k 的最小堆：堆里始终是"目前见过的前 k 大元素"
  2. 堆顶是最小值：最小堆的堆顶永远是堆内最小，即前 k 大里的"第 k 大"
  3. 填满之前：直接 offer 入堆，不比较
  4. 填满之后：新元素 > 堆顶才替换（poll 弹出堆顶 + offer 加入新元素），否则丢弃
  5. 堆内自动维护：offer 和 poll 内部通过上浮/下沉操作维持最小堆形态，不需要手动管理
  6. **时间复杂度 O(n log k)**：每个元素最多一次入堆/出堆，单次代价 O(log k)

四、思路详解

第一步：为什么维护 k 大小的列表就能找到第 k 大？

第 k 大的定义是什么？是"把所有元素从大到小排，排在第 k 位的那个"。换句话说，全数组里只有 k - 1 个元素比它大。

那如果我们手里始终保留着遍历至今最大的 k 个元素：

  • 这 k 个元素内部排个序，最小的那个，前面正好有 k - 1 个比它大的（都在堆里）

  • 它就是第 k 大

用 nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]，k = 4 完整走一遍：

1
2
3
4
5
6
7
8
9
10
11
12
遍历元素      列表内容（k=4）      最小值    操作
   3          [3]                 -        未满，直接加入
   2          [3,2]               -        未满，直接加入
   3          [3,2,3]             -        未满，直接加入
   1          [3,2,3,1]           1        未满，直接加入（满了）
   2          [3,2,3,2]           2        2 > 1，替换 1
   4          [3,4,3,2]           2        4 > 2，替换 2
   5          [3,4,3,5]           3        5 > 2，替换 2
   5          [4,3,5,5]           3        5 > 3，替换 3
   6          [4,5,5,6]           4        6 > 3，替换 3

遍历结束 → 列表 [4,5,5,6]，最小值 4 → 第 4 大 = 4 ✓

思路成立。但注意上面每一步的"最小值"这一列——每次替换后最小值都可能变化，普通列表每次都要重新扫一遍才能知道最小值是谁。

第二步：朴素列表的问题

问题拆开看：

  1. 每来一个新元素，都要找列表的最小值来比较 → 扫 k 个元素，O(k)
  2. 替换掉最小值后，新的最小值是谁？ → 又要扫一遍，O(k)

n 个元素就是 O(n × k)。当 k 接近 n 时，接近 O(n²)，比直接排序还慢。

我们需要的数据结构：

  • 能 O(1) 拿到最小值（比较用）

  • 替换最小值后，能快速（O(log k) 以内）维护出新的最小值

这正好就是最小堆的两个核心能力。

第三步：最小堆——物理是数组，逻辑是完全二叉树

最小堆的物理存储就是一个普通的连续数组：

1
2
A  B  C  D  E  F  G  H  I        ← 数组元素
0  1  2  3  4  5  6  7  8        ← 下标

但它们之间的逻辑关系是一棵完全二叉树：按一层一层的顺序排列（其实就是 BFS 的顺序），第 0 层是 A，第 1 层是 B、C，第 2 层依次类推。

1
2
3
4
5
6
7
           A(0)
         /      \
     B(1)        C(2)
     /   \      /    \
  D(3)  E(4)  F(5)  G(6)
  /  \
H(7)  I(8)

再维护一条核心性质：父节点的值 ≤ 子节点的值（父比两个孩子都小）。

这条性质一层层往上推，就能保证堆顶（锥顶）就是最小值——这就是我们要的 O(1) 拿最小值。

为什么要组织成完全二叉树？ 就是为了减小比较和维护最小值的时间复杂度：后面的下沉、上浮操作，每一层最多只和 1~2 个元素比较，一趟最多走树高，也就是 O(log k)；如果用普通列表，每次找最小值都要扫全部 k 个元素，是 O(k)。

第四步：索引公式怎么来的？

对于数组中下标为 i 的节点：

1
2
3
左孩子 = 2i + 1
右孩子 = 2i + 2
父节点 = (i - 1) / 2

推导：完全二叉树按层排列，下标 0 到 i-1 一共 i 个节点，每个节点都有两个孩子，所以前面这些节点的孩子一共 2i 个，它们按顺序占据下标 1 到 2i。轮到节点 i 的孩子，自然从 2i + 1 开始。

验证：

1
2
3
4
5
6
i    左孩子(2i+1)    右孩子(2i+2)    父节点((i-1)/2)
0        1                2               -
1        3                4               0
2        5                6               0
3        7                8               1
4        9               10               1

对照上面的树形图：B(1) 的孩子是 D(3)、E(4) ✓，C(2) 的孩子是 F(5)、G(6) ✓。

有了公式，数组就能当树用，不需要任何指针。

第五步：下沉——弹出堆顶后恢复最小堆

替换最小值的第一个动作是弹出堆顶。但堆顶空出来之后，怎么补？

做法：把数组末尾元素提到堆顶，然后执行下沉操作。

为什么末尾元素提上来之后堆顶可能不再是最小值？因为它原本在叶子位置，大小 arbitrary，提到堆顶后可能比孩子大，违反"父 ≤ 子"的性质。

下沉的具体步骤：

  1. 看当前节点的左右孩子（用公式 2i+1、2i+2），先找出两个孩子中的较小值
  2. 如果当前节点 > 较小孩子 → 交换，然后继续对交换后的位置下沉
  3. 直到没有孩子，或者比两个孩子都小 → 停止

演示：最小堆 [1, 4, 3, 5, 6] 弹出堆顶 1

1
2
3
4
5
6
7
8
弹出前：                 末尾 6 提到堆顶：
        1                        6
      /   \                    /   \
     4     3                  4     3
    / \                      /
   5   6                    5

数组：[1, 4, 3, 5, 6]        数组：[6, 4, 3, 5]

下沉过程：

1
2
3
4
5
6
7
8
9
10
11
12
第 1 轮：6 的孩子是 4 和 3，较小值 3，6 > 3 → 交换

        3
      /   \
     4     6
    /
   5

数组：[3, 4, 6, 5]

第 2 轮：6（下标2）的孩子在下标 5 和 6，
数组长度只有 4，孩子不存在 → 停止

最终堆 [3, 4, 6, 5]：3 ≤ 4、6，4 ≤ 5，最小堆性质保持，堆顶 3 就是新的最小值。

每轮最多和两个孩子比较，一路沉到叶子，最多走树高步 = O(log k)。

第六步：上浮——加入新元素后恢复最小堆

弹出堆顶之后，第二个动作是加入新元素。我们并不知道新元素是不是新的最小值，所以要再比较、重新维护。

做法：把新元素放到数组末尾，然后执行上浮操作。

新元素在末尾，必然是某个节点的左孩子或右孩子，用公式 (i-1)/2 直接定位它的父节点。

上浮的具体步骤：

  1. 找到父节点 (i-1)/2
  2. 如果当前节点 < 父节点 → 交换，继续对交换后的位置上浮
  3. 直到比父节点大，或者到达堆顶 → 停止

为什么只和父节点比，不和兄弟节点比？

因为"父 ≤ 两个孩子"是既有性质，如果新元素比父节点还小，那必然也比兄弟小（父本来就是两个孩子里较小的参照）。和兄弟比没有意义，比父节点就够了。

演示：往 [3, 4, 5, 6] 加入新元素 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
加入末尾：                上浮第 1 轮：
        3                        3
      /   \                    /   \
     4     5                  2     5
    / \                      / \
   6   2                    6   4
                             ↑
                        2 < 4，交换

数组：[3, 4, 5, 6, 2]        数组：[3, 2, 5, 6, 4]

上浮第 2 轮：
        2
      /   \
     3     5
    / \
   6   4
   ↑
2 < 3（堆顶），交换

数组：[2, 3, 5, 6, 4]

第 3 轮：2 已到堆顶，没有父节点 → 停止

上浮同样最多走树高步 = O(log k)。

完整执行过程

以 nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]，k = 4 为例：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
初始：minHeap = []

num=3：size(0) < 4，直接入堆
  minHeap = [3]

        3

num=2：size(1) < 4，直接入堆
  加到末尾 [3, 2]，2 是 3 的左孩子，2 < 3 上浮交换
  minHeap = [2, 3]

        2
       /
      3

num=3：size(2) < 4，直接入堆
  加到末尾 [2, 3, 3]，3 的父节点是 2，3 > 2 不动
  minHeap = [2, 3, 3]

        2
      /   \
     3     3

num=1：size(3) < 4，直接入堆
  加到末尾 [2, 3, 3, 1]，1 的父节点是 3，交换 → [2, 1, 3, 3]
  1 的父节点是 2，交换 → [1, 2, 3, 3]（堆满）
  minHeap = [1, 2, 3, 3]

        1
      /   \
     2     3
    /
   3

num=2：2 > 堆顶 1 → 弹出 1，加入 2
  弹出：末尾 3 提顶 [3, 2, 3] → 下沉与 2 交换 → [2, 3, 3]
  加入：加到末尾 [2, 3, 3, 2] → 2 与父节点 3 交换 → [2, 2, 3, 3]
  minHeap = [2, 2, 3, 3]

        2
      /   \
     2     3
    /
   3

num=4：4 > 堆顶 2 → 弹出 2，加入 4
  弹出：末尾 3 提顶 [3, 2, 3] → 下沉与 2 交换 → [2, 3, 3]
  加入：加到末尾 [2, 3, 3, 4] → 4 > 父节点 3 不动
  minHeap = [2, 3, 3, 4]

        2
      /   \
     3     3
    /
   4

num=5：5 > 堆顶 2 → 弹出 2，加入 5
  弹出：末尾 4 提顶 [4, 3, 3] → 下沉与 3 交换 → [3, 4, 3]
  加入：加到末尾 [3, 4, 3, 5] → 5 > 父节点 4 不动
  minHeap = [3, 4, 3, 5]

        3
      /   \
     4     3
    /
   5

num=5：5 > 堆顶 3 → 弹出 3，加入 5
  弹出：末尾 5 提顶 [5, 4, 3] → 下沉与 3 交换 → [3, 4, 5]
  加入：加到末尾 [3, 4, 5, 5] → 5 > 父节点 4 不动
  minHeap = [3, 4, 5, 5]

        3
      /   \
     4     5
    /
   5

num=6：6 > 堆顶 3 → 弹出 3，加入 6
  弹出：末尾 5 提顶 [5, 4, 5] → 下沉与 4 交换 → [4, 5, 5]
  加入：加到末尾 [4, 5, 5, 6] → 6 > 父节点 5 不动
  minHeap = [4, 5, 5, 6]

        4
      /   \
     5     5
    /
   6

遍历结束，堆顶 = 4 → 第 4 大 = 4 ✓

复杂度分析

**时间复杂度 O(n log k)**：

  • 每个元素最多一次入堆 + 一次出堆

  • 入堆和出堆的代价都是树高，即 O(log k)

  • n 个元素，总共 O(n log k)

当 k 远小于 n 时（比如 k = 100，n = 100 万），log k 远小于 log n，比整体排序的 O(n log n) 快得多。

**空间复杂度 O(k)**：堆内最多 k 个元素。

对比排序方案：时间 O(n log n)、空间 O(log n)（快排递归栈）。堆方案在 k 小的时候全面占优，而且代码极短。

五、总结

数组中的第K个最大元素的核心思路：

  1. 转换视角：第 k 大 = "前 k 大元素中的最小值"，维护一个大小为 k 的容器即可
  2. 相同值占位：[6,5,5,4...] 中两个 5 各占一个位置，第 4 大是 4
  3. 最小堆：物理是数组，逻辑是完全二叉树，父 ≤ 子，堆顶即最小值
  4. 索引公式：左孩子 2i+1，右孩子 2i+2，父节点 (i-1)/2
  5. 下沉：弹出堆顶后，末尾元素提到堆顶，和较小孩子一路换下去
  6. 上浮：新元素放末尾，只和父节点比（比父小必然比兄弟小），一路换上来
  7. Java 封装：PriorityQueue 就是最小堆，offer/poll 自动上浮/下沉

Top K 问题的通用套路：

  • 找第 k 大 / 前 k 大 → 大小为 k 的最小堆（堆顶是门槛）

  • 找第 k 小 / 前 k 小 → 大小为 k 的最大堆

记住"堆顶是门槛"：想留大的，门槛就得是最小值（最小堆）；想留小的，门槛就得是最大值（最大堆）。