跳到主要内容

堆 (Heap)

堆是一种优先队列的具体实现，常用于解决 Top-K 元素查找、合并有序队列、寻找动态中位数等问题。

215. 数组中的第K个最大元素 (Kth Largest Element in an Array)​

题目描述​

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

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路​

最小堆维护 Top-K。

  1. 建立一个容量为 k 的最小堆（PriorityQueue 默认实现）。
  2. 遍历数组，将元素加入堆中。
  3. 如果堆的大小超过 k，弹出堆顶元素（弹出的必是当前最小的）。
  4. 遍历结束后，堆顶即为第 k 个最大的。

Java 代码实现​

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : nums) {
            pq.offer(x);
            if (pq.size() > k) pq.poll();
        }
        return pq.peek();
    }
}

502. IPO (IPO)​

题目描述​

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个项目后能得到的最大总资本。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目，以最大化最终资本 ，并输出最终可获得的最多资本。

解题思路​

按最小成本排序 + 最大利润堆。

  1. 将所有项目按 cost 升序排列。
  2. 循环最多 kk 次（或能开启项目的所有次数）：
    • 将所有 cost <= w（当前拥有的资本）的项目对应的 profit 加入最大堆。
    • 如果最大堆为空（买不起了），跳出。
    • 弹出堆顶（当前可买的最大利润），加到 w 中。

Java 代码实现​

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) projects[i] = new int[]{capital[i], profits[i]};
        Arrays.sort(projects, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int i = 0;
        while (k-- > 0) {
            while (i < n && projects[i][0] <= w) pq.offer(projects[i++][1]);
            if (pq.isEmpty()) break;
            w += pq.poll();
        }
        return w;
    }
}

373. 查找和最小的 K 对数字 (Find K Pairs with Smallest Sums)​

题目描述​

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。

解题思路​

堆 + 多路归并 (Multi-way Merge)。

  1. 建立最小堆。最初将 (nums1[i], nums2[0]) 入堆，其中 i 从 0 到 min(k, nums1.length)-1。
  2. 每一个堆元素记录为 [i, j]，表示 nums1[i] + nums2[j]。
  3. 弹出堆顶（最小和），记录到结果集中。
  4. 如果该点还有下一个 j（即 j + 1 < nums2.length），则将 [i, j + 1] 入堆。
  5. 重复 kk 次。

Java 代码实现​

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]]));
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            pq.offer(new int[]{i, 0});
        }
        List<List<Integer>> res = new ArrayList<>();
        while (k-- > 0 && !pq.isEmpty()) {
            int[] idx = pq.poll();
            res.add(Arrays.asList(nums1[idx[0]], nums2[idx[1]]));
            if (idx[1] + 1 < nums2.length) {
                pq.offer(new int[]{idx[0], idx[1] + 1});
            }
        }
        return res;
    }
}

295. 数据流的中位数 (Find Median from Data Stream)​

题目描述​

中位数 是有序列中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

  • 例如， [2,3,4] 的中位数是 3
  • 例如， [2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

解题思路​

双堆共存策略。

  • maxHeap（大顶堆）：记录数据流的较小那一半，堆顶即为左侧最大。
  • minHeap（小顶堆）：记录数据流的较大那一半，堆顶即为右侧最小。
  1. 保持两个堆的数量之差不超过 1。
  2. 插入时调整：先插入一个堆再转插到另一个。
  3. 如果 size 相同，均值；否则返回较大的那个堆顶。

Java 代码实现​

class MedianFinder {
    PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);
    PriorityQueue<Integer> right = new PriorityQueue<>();

    public void addNum(int num) {
        if (left.size() == right.size()) {
            right.offer(num); left.offer(right.poll());
        } else {
            left.offer(num); right.offer(left.poll());
        }
    }
    public double findMedian() {
        if (left.size() == right.size()) return (left.peek() + right.peek()) / 2.0;
        return left.peek();
    }
}

(注：左堆（大的那一半里的最小堆）和右堆（小的那一半里的大堆）根据习惯设定，上述代码将偏大那一半放在左边大的堆里)。 Wait, left (max heap) is smaller half, right (min heap) is larger half. Correct. If left.size > right.size, median is left.peek. Correct. If even, median is average. Correct.