手帐 Blog

主题

复盘 · LC 215 数组中的第K个最大元素 ​

题目 ​

题意 ​

给定整数数组 nums 和整数 k，返回数组中第 k 个最大的元素（不是第 k 个不同元素）。

  • 例如 [3,2,1,5,6,4]、k=2 → 第 2 大是 5。
  • 约束：1 <= k <= nums.length，长度可达 10⁵。

涉及算法 ​

标签一句话
堆（最小堆）维护大小为 k 的最小堆，堆顶就是第 k 大
快速选择快排分区，只递归一侧，平均 O(n)
排序排序后取 nums[n-k]，O(n log n) 兜底

教程延伸：09 · 哈希表进阶 练习清单里的 347（前 K 高频）同用堆思想。

评价我的解法 ​

你的思路：用最小堆保留最大的 k 个数，堆顶即第 k 大——套路选对。但主函数在「替换」时只 insert、没先弹出堆顶，堆会超过 k 个元素，答案错误。

我的代码（摘自 215-数组中的第K个最大元素/index.js，主函数 + 堆类要点；不含测例）：

javascript
var findKthLargest = function (nums, k) {
  const heap = new YangMinHeap(nums.slice(0, k));
  for (let i = k; i < nums.length; i++) {
    const num = nums[i];
    if (num <= heap.peek()) {
      continue;
    }
    heap.insert(num);
  }
  return heap.peek();
};

class YangMinHeap {
  constructor(arr = []) {
    this.heap = [];
    if (arr.length > 0) {
      this.heap = [...arr];
      this._heapify();
    }
  }
  insert(value) {
    this.heap.push(value);
    this._siftUp(this.heap.length - 1);
  }
  peek() {
    return this.heap.length === 0 ? null : this.heap[0];
  }
  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._siftDown(0);
    return min;
  }
  // _siftUp / _siftDown / _heapify 实现完整，此处略
}

错在哪（关键）

本地 nums = [3,2,1,5,6,4]、k = 2：输出 2，正确应为 5。

原因：num > heap.peek() 时直接 insert，没有 extractMin()。堆从 k 个涨到 n 个，堆顶一直是全局最小值 2，不是「第 k 大」。

正确替换应是：

javascript
if (num > heap.peek()) {
  heap.extractMin();
  heap.insert(num);
}

对在哪

  1. 选题方向对：第 K 大 → 大小为 k 的最小堆，不是最大堆全排序。
  2. YangMinHeap 类里 siftUp / siftDown / Floyd heapify 结构完整，说明你在借用的堆实现本身是合格的。
  3. 注释里诚实写「堆不是我写的」——下一步是把调用堆的业务逻辑自己默写出来。

复杂度（若修好替换逻辑）：建堆 O(k)，后续每个元素最多一次弹+插 → O(n log k) 时间，O(k) 空间。

最佳题解 ​

大小为 k 的最小堆（面试先讲这个）：

javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const heap = nums.slice(0, k);
  heapify(heap);

  for (let i = k; i < nums.length; i++) {
    if (nums[i] > heap[0]) {
      heap[0] = nums[i];
      siftDown(heap, 0);
    }
  }
  return heap[0];
};

function siftDown(heap, i) {
  const n = heap.length;
  while (true) {
    let smallest = i;
    const l = 2 * i + 1;
    const r = 2 * i + 2;
    if (l < n && heap[l] < heap[smallest]) smallest = l;
    if (r < n && heap[r] < heap[smallest]) smallest = r;
    if (smallest === i) break;
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    i = smallest;
  }
}

function heapify(arr) {
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    siftDown(arr, i);
  }
}
  • 时间 O(n log k)，空间 O(k)。
  • 为何更优：堆大小恒为 k；只下沉堆顶完成「踢掉最小、放入更大」，无需完整 extractMin + insert 两次调整也可（上式等价）。

快选平均 O(n)、最坏 O(n²)，面试进阶可讲；排序 O(n log n) 作兜底一句即可。

关联题目 ​

题为何相关
347. 前 K 个高频元素计数 + 大小为 k 的堆
703. 数据流中的第 K 大元素同一最小堆，数据流版
912. 排序数组快选/堆排序练手

一句话带走 ​

第 K 大：维护大小为 k 的最小堆，新数比堆顶大就先弹堆顶再插入（或改堆顶下沉），最后堆顶就是答案。