堆

LeetCode 295 https://leetcode.cn/problems/find-median-from-data-stream/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 需要两个堆。left 是最大堆，right 是最小堆。 保证 left 的大小和 right 的大小尽量相等。规定：在有奇数个数时，left 比 right 多 1 个数。 保证 left 的所有元素都小于等于 right 的所有元素。 如果当前有奇数个元素，中位数是 left 的堆顶。 如果当前有偶数个元素，中位数是 left 的堆顶和 right 的堆顶的平均值。 如果当前 left 的大小和 right 的大小相等： 如果添加的数字 num 比较大，比如添加 7，那么把 7 加到 right 中。现在 left 比 right 少 1 个数，不符合前文的规定，所以必须把 right 的最小值从 right 中去掉，添加到 left 中。如此操作后，可以保证 left 的所有元素都小于等于 right 的所有元素。 如果添加的数字 num 比较小，比如添加 0，那么把 0 加到 left 中。 这两种情况可以合并：无论 num 是大是小，都可以先把 num 加到 right 中，然后把 right 的最小值从 right 中去掉，并添加到 left 中。 如果当前 left 比 right 多 1 个数： 如果添加的数字 num 比较大，比如添加 7，那么把 7 加到 right 中。 如果添加的数字 num 比较小，比如添加 0，那么把 0 加到 left 中。现在 left 比 right 多 2 个数，不符合前文的规定，所以必须把 left 的最大值从 left 中去掉，添加到 right 中。如此操作后，可以保证 left 的所有元素都小于等于 right 的所有元素。 这两种情况可以合并：无论 num 是大是小，都可以先把 num 加到 left 中，然后把 left 的最大值从 left 中去掉，并添加到 right 中。 时间复杂度：初始化和 findMedian 都是 O(1)，addNum 是 O(logq)，其中 q 是 addNum 的调用次数。每次操作堆需要 O(logq) 的时间。 空间复杂度：O(q)。 ...

LeetCode 23 https://leetcode.cn/problems/merge-k-sorted-lists/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是最小堆的题目。首先将 k 个链表的头节点加入堆，每次在链表中插入堆顶元素，再把堆顶元素的下一个元素入堆。 需要注意的是最小堆的声明方式。a > b（greater）是最小堆，a < b（less） 是最大堆。STL 的优先队列默认是最大堆。 auto cmp = [](const ListNode* a, const ListNode* b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq; 时间复杂度：O(Llogm)，其中 m 为 lists 的长度，L 为所有链表的长度之和。 空间复杂度：O(m)。堆中至多有 m 个元素。 ...