堆与贪心的本质区别
在刷题中，堆（Heap）和贪心（Greedy）常被并列提及，但它们的应用场景截然不同：
- 堆（优先队列）：适用于 维护动态数据集的极值，如求 TopK、中位数、动态排序等。堆本身是一种数据结构，不涉及决策逻辑，只提供高效的插入和获取极值操作。
- 贪心算法：适用于具有 最优子结构 和 贪心选择性质 的问题，每一步做出当前局部最优选择，最终累积为全局最优。贪心是一种算法思想，需要证明正确性。
LeetCode 热门 100 题中，有四题分别代表了这两类：215. 数组中的第K个最大元素、347. 前K个高频元素、295. 数据流的中位数 属于堆的经典应用；763. 划分字母区间 则是贪心的典型代表。下面逐一剖析。
1. 数组中的第K个最大元素（LeetCode 215）
题目：给定整数数组 nums 和整数 k，返回数组中第 k 个最大的元素。
堆解法：维护一个大小为 k 的小顶堆，堆顶即为第 k 大元素。时间复杂度 O(n log k)，空间 O(k)。
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) minHeap.poll();
}
return minHeap.peek();
}
关键点：使用小顶堆存储最大的 k 个数，堆顶是第 k 大。这不是贪心，因为最终结果依赖于全局数据，而非逐步局部决策。
2. 前K个高频元素（LeetCode 347）
题目：给定数组 nums 和整数 k，返回出现频率前 k 高的元素。
堆解法：哈希统计频率，再用大小为 k 的小顶堆按频率筛选。
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
minHeap.offer(new int[]{e.getValue(), e.getKey()});
if (minHeap.size() > k) minHeap.poll();
}
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = minHeap.poll()[1];
return res;
}
关键点：同样基于全局统计，与贪心无关。
3. 数据流的中位数（LeetCode 295）
题目：设计数据结构，支持添加整数，并随时获取当前所有元素的中位数。
双堆解法：一个大顶堆存较小的一半，一个小顶堆存较大的一半，保持平衡，中位数为堆顶值。
class MedianFinder {
private PriorityQueue<Integer> maxHeap; // 存较小的一半
private PriorityQueue<Integer> minHeap; // 存较大的一半
public MedianFinder() {
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() > minHeap.size()) return maxHeap.peek();
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
}
关键点：中位数依赖于全部数据，堆只是高效维护有序性，并非贪心决策。
4. 划分字母区间（LeetCode 763）
题目：给定字符串 s，将字符串划分为尽可能多的片段，使得每个字母最多出现在一个片段中。返回每个片段的长度。
贪心思路：
- 先统计每个字符最后出现的位置
lastPos。 - 遍历字符串，维护当前片段的右边界
right = max(right, lastPos[s[i]])。 - 当
i == right时，说明当前片段已经结束，记录长度，并更新左边界。
为什么是贪心？ 每一步我们都尽可能地延长当前片段的右边界，使当前片段包含所有已出现字符的最后位置，直到无法再延伸。这种"能延伸就延伸"的策略，保证了每段尽可能长，从而片段数尽可能多，是局部最优累积到全局最优的典型。
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
List<Integer> res = new ArrayList<>();
int start = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
right = Math.max(right, last[s.charAt(i) - 'a']);
if (i == right) {
res.add(i - start + 1);
start = i + 1;
}
}
return res;
}
复杂度：O(n)，空间 O(1)（固定 26）。
关键点：每一步更新当前片段的最终边界，当到达边界时切割，保证当前片段是满足条件的最短前缀，从而使得后续片段能尽可能多，是贪心选择性质的体现。
四题对比与启发
| 题目 | 核心技巧 | 算法类型 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 215. 第K大元素 | 小顶堆 | 堆 | O(n log k) | O(k) |
| 347. 前K高频 | 哈希 + 小顶堆 | 堆 | O(n log k) | O(n) |
| 295. 数据流中位数 | 双堆 | 堆 | O(log n) 插入 | O(n) |
| 763. 划分字母区间 | 贪心（最后位置） | 贪心 | O(n) | O(1) |
共同本质：前三题都是 数据筛选/排序类 问题，堆提供了高效的极值维护；最后一题是 区间划分类 问题，贪心利用"最后一个位置"的单调性，一次性确定切分点。
总结：何时用堆，何时用贪心？
- 堆：当问题中出现 “第K大/小”、“前K个”、“中位数”、“动态极值” 等关键词时，优先考虑堆。堆擅长处理流式数据或大规模数据的 TopK 筛选。
- 贪心：当问题具有 “每一步选择局部最优，不影响后续决策可行性” 的性质时，考虑贪心。常见特征包括区间覆盖、跳跃游戏、活动选择、字符串划分等。