【数据结构与算法体系】之贪心算法

一、贪心算法的核心思想

贪心算法（Greedy Algorithm）在每一步选择中都采取当前状态下看起来最优的选择，期望通过一系列局部最优决策最终达到全局最优解。贪心算法的精妙之处在于——对于某些问题，这种“短视”的策略恰好能得到全局最优解；但对于另一些问题，贪心策略可能导致很差的解。

贪心算法适用的问题必须满足两个关键性质。贪心选择性质（Greedy-Choice Property）：全局最优解可以通过一系列局部最优选择来构造。也就是说，第一个贪心选择不会排除全局最优解的可能性——存在一个包含该贪心选择的全局最优解。最优子结构（Optimal Substructure）：做出贪心选择后，剩下的子问题与原问题具有相同的形式，且子问题的最优解可以与贪心选择组合成原问题的最优解。

贪心算法与动态规划的重要区别：DP系统地探索所有可能的决策组合（通过状态转移方程），保证找到全局最优；贪心算法在每个步骤仅做一次选择且不回溯，因此只有在问题具有贪心选择性质时才保证正确。验证贪心策略的正确性是贪心算法最核心的难点——需要严格的数学证明（通常使用“交换论证”或“贪心领先”证明技术）。

二、活动选择问题

活动选择问题（Activity Selection）是贪心算法的经典入门问题：给定N个活动，每个活动有开始时间s[i]和结束时间f[i]。同一时间只能进行一个活动，求最多能安排多少个互不重叠的活动。

贪心策略：按结束时间最早优先选择。每次选择当前未选的活动中结束时间最早且不与已选活动冲突的活动。为什么这个策略是最优的？交换论证：假设存在一个最优解，我们可以将它的第一个活动替换为我们贪心选择的第一个活动（因为贪心选择的活动结束时间不晚于最优解的第一个活动），替换后不减少可安排的活动数量。依此类推，贪心解的活动数量至少等于任何最优解的活动数量。

int activitySelection(int[] s, int[] f) {
    int n = s.length;
    Integer[] indices = new Integer[n];
    for (int i = 0; i < n; i++) indices[i] = i;
    Arrays.sort(indices, Comparator.comparingInt(i -> f[i]));
    
    int count = 1;
    int lastFinish = f[indices[0]];
    for (int i = 1; i < n; i++) {
        if (s[indices[i]] >= lastFinish) {
            count++;
            lastFinish = f[indices[i]];
        }
    }
    return count;
}

时间复杂度O(N log N)（主要由排序决定），空间复杂度O(N)。注意如果活动已按结束时间排序，贪心选择可以在O(N)时间内完成。

三、霍夫曼编码

霍夫曼编码（Huffman Coding）是一种最优前缀编码，用于数据压缩。给定每个字符出现的频率，构建一棵二叉树，使频率高的字符用较短的编码，频率低的字符用较长的编码，从而使得编码总长度最小化。前缀码的性质是没有任何一个字符的编码是另一个字符编码的前缀，这保证了解码的确定性。

贪心策略：每次从频率表中取出频率最小的两个节点，合并为一个新节点（频率为两者之和）。重复这个过程直到只剩一个节点（霍夫曼树的根）。

class HuffmanNode implements Comparable<HuffmanNode> {
    char ch;
    int freq;
    HuffmanNode left, right;
    
    HuffmanNode(char ch, int freq) {
        this.ch = ch; this.freq = freq;
    }
    
    HuffmanNode(int freq, HuffmanNode left, HuffmanNode right) {
        this.freq = freq; this.left = left; this.right = right;
    }
    
    public int compareTo(HuffmanNode other) {
        return this.freq - other.freq;
    }
    
    boolean isLeaf() { return left == null && right == null; }
}

HuffmanNode buildHuffmanTree(Map<Character, Integer> freqMap) {
    PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
    for (var entry : freqMap.entrySet()) {
        pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
    }
    
    while (pq.size() > 1) {
        HuffmanNode left = pq.poll();
        HuffmanNode right = pq.poll();
        pq.offer(new HuffmanNode(left.freq + right.freq, left, right));
    }
    return pq.poll(); // 根节点
}

void generateCodes(HuffmanNode node, String code, Map<Character, String> codeMap) {
    if (node == null) return;
    if (node.isLeaf()) {
        codeMap.put(node.ch, code);
    } else {
        generateCodes(node.left, code + "0", codeMap);
        generateCodes(node.right, code + "1", codeMap);
    }
}

为什么霍夫曼编码是最优的？核心证明思路：在最优的前缀码树中，频率最低的两个字符一定位于最深的一层且是兄弟节点（交换论证——如果把频率更低的字符放到更深的位置，总编码长度只会更小或相等）。因此合并这两个字符的贪心选择一定不会错过最优解。

霍夫曼编码在现实世界中被广泛使用：JPEG图像压缩、MP3音频压缩、PKZIP/GZIP等压缩工具、DEFLATE算法（结合LZ77和霍夫曼编码）。

四、Dijkstra最短路径算法

Dijkstra算法求解非负权有向图中从单个源点到所有其他顶点的最短路径。Dijkstra算法本质上是一种贪心算法——每次都选择当前距离最小的未确定顶点，将其标记为“已确定”（其距离不再更新），并对其所有出边进行松弛（Relaxation）操作。

int[] dijkstra(Graph graph, int source) {
    int V = graph.V;
    int[] dist = new int[V];
    boolean[] visited = new boolean[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;
    
    // PriorityQueue 按距离排序，(顶点, 距离)
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{source, 0});
    
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int v = cur[0];
        if (visited[v]) continue;  // 懒惰删除
        visited[v] = true;
        
        for (Edge e : graph.adj[v]) {
            int u = e.to;
            if (!visited[u] && dist[v] + e.weight < dist[u]) {
                dist[u] = dist[v] + e.weight;
                pq.offer(new int[]{u, dist[u]});
            }
        }
    }
    return dist;
}

Dijkstra算法使用二叉堆实现优先队列时，时间复杂度为O((V + E) log V)。如果使用斐波那契堆，理论上可以做到O(V log V + E)。在实践中，二叉堆版本是最常用的。

Dijkstra算法的贪心正确性：为什么每次可以安全地将距离最小的顶点标记为“已确定”？假设算法首次错误地将顶点v标记为已确定，即存在另一条经过某些未确定顶点的更短路径。设v是当前距离最小的未确定顶点，任何经过未确定顶点的路径都需要额外经过别的未确定顶点w，而dist[w] ≥ dist[v]（因为v是当前最小值），加上w到v的非负权重，总长度不可能小于dist[v]。这里“非负权重”条件是关键——Dijkstra算法不能处理负权边，因为如果有负权边，经过更多顶点的路径可能反而更短。

五、Prim的最小生成树

最小生成树（Minimum Spanning Tree，MST）是连接无向连通图中所有顶点的权重和最小的边的子集（形成一棵树）。Prim算法从任意顶点开始，不断选择权重最小的边连接已选顶点集合与未选顶点集合，直到所有顶点都被连接。

int primMST(Graph graph) {
    int V = graph.V;
    boolean[] inMST = new boolean[V];
    int[] minEdge = new int[V]; // 连接未选顶点到已选集合的最小边权
    Arrays.fill(minEdge, Integer.MAX_VALUE);
    minEdge[0] = 0;
    
    int totalWeight = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{0, 0}); // (顶点, 权重)
    
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int v = cur[0];
        if (inMST[v]) continue;
        inMST[v] = true;
        totalWeight += cur[1];
        
        for (Edge e : graph.adj[v]) {
            int u = e.to;
            if (!inMST[u] && e.weight < minEdge[u]) {
                minEdge[u] = e.weight;
                pq.offer(new int[]{u, e.weight});
            }
        }
    }
    return totalWeight;
}

Prim算法与Dijkstra算法在代码结构上惊人地相似——唯一的区别在于优先级键值的含义：Dijkstra中是“从源点到该顶点的最短距离”，Prim中是“该顶点到已选集合的最小边权”。两者都是贪心算法，但贪心的目标和证明不同。

六、Kruskal的最小生成树与并查集

Kruskal算法是另一种MST算法：将所有边按权重升序排序，依次考虑每条边，如果加入该边不会形成环，则将其加入MST。判断“是否形成环”使用并查集（Union-Find / Disjoint Set Union，DSU）数据结构。

class UnionFind {
    int[] parent;
    int[] rank;
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    public boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false; // 已连通
        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        return true;
    }
}

int kruskalMST(int V, List<Edge> edges) {
    Collections.sort(edges, Comparator.comparingInt(e -> e.weight));
    UnionFind uf = new UnionFind(V);
    int totalWeight = 0;
    int count = 0; // 已选的边数
    
    for (Edge e : edges) {
        if (uf.union(e.from, e.to)) {
            totalWeight += e.weight;
            count++;
            if (count == V - 1) break; // MST已完成
        }
    }
    return totalWeight;
}

Kruskal算法的时间复杂度为O(E log E)（排序占主导）。在稀疏图中（E ≈ V），Kruskal比Prim更高效（O(V log V) vs O(V²)朴素版）；在稠密图中，Prim的朴素实现O(V²)可能更优（因为不需要对所有边排序）。实际应用中，Prim使用二叉堆和Kruskal使用排序各有适用场景。

七、贪心算法的证明方法

贪心算法的最大挑战在于证明其正确性。面试中，仅仅说出贪心策略是不够的，需要能够说服面试官该策略确实能得到最优解。两种经典证明方法：

交换论证（Exchange Argument）：假设存在一个最优解OPT，我们逐步将OPT中的决策替换为贪心算法的决策，证明每次替换不会使解的质量变差。最终得到贪心解G，而G的质量不差于OPT，因此G也是最优的。活动选择问题的证明就是交换论证的典型应用。

贪心领先（Greedy Stays Ahead）：证明贪心算法在每一步之后都不比任何最优解“差”。通常通过维护贪心解和最优解之间的某种顺序关系（如“贪心算法处理完前k个元素后，其某个度量指标至少与最优解一样好”）。区间调度问题的另一种证法就是使用贪心领先——证明贪心算法在第k步选择的活动的结束时间不晚于任何最优解在第k步选择的活动的结束时间。

某些问题中贪心算法不能保证最优解，但可能是一个好的近似算法。例如，0/1 背包问题中，贪心策略（按单位重量价值降序选择）不保证最优，但它对分数背包问题是正确的（分数背包中物品可以分割，贪心策略最优）。在面试中，诚实地区分“贪心可行”和“贪心近似”可以展示出算法的深度理解。

八、面试常见追问

问题一：Dijkstra算法为什么不能处理负权边？

Dijkstra基于“已确定顶点的距离不再更新”的不变性。当存在负权边时，这个不变性被破坏——经过更多顶点的路径可能由于负权边的抵消作用而更短。考虑一个简单例子：A→B权3，A→C权2，C→B权-2。从A出发，Dijkstra首先确定C（距离2），然后从C松弛B，B的距离更新为2 + (-2) = 0。但此时B的距离（0）小于之前“已确定”的C的距离（2），违反了不变性。对于含负权边的图，应使用Bellman-Ford算法（O(VE)），它能正确处理负权边并检测负权环。

问题二：Prim算法和Kruskal算法在实际中如何选择？

Prim适合稠密图（E接近V²），其朴素的O(V²)实现（不使用堆，直接扫描minEdge数组）在稠密图上因常数因子小而非常快。Kruskal适合稀疏图（E接近V），因为排序O(E log E) ≈ O(V log V)的开销可以接受，且并查集操作几乎是常数时间。另外，如果边已经按权值存储（如输入来自排序好的文件），或者图以边列表而非邻接表给出，Kruskal更自然。内存方面，Kruskal需要存储所有边，在极大图上可能超出内存；Prim只需邻接表。

问题三：如何判断一个问题是否可以用贪心解决？

首先，检查问题是否具有最优子结构——全局最优解能否由局部决策逐步构造。其次，尝试设计贪心策略并验证贪心选择性质——是否存在一种局部最优选择，使得做出该选择后，剩余子问题的最优解加上该选择能得到原问题的全局最优解。反例测试是快速判断贪心是否可行的方法——尝试构造一个反例，使得看似合理的贪心策略失败。例如，对于硬币找零问题，如果硬币面值为[1, 3, 4]，金额为6，贪心策略“每次选最大面值”会选择4+1+1=6（3枚硬币），但最优解是3+3=6（2枚硬币）。这个反例表明普通的贪心策略在该硬币体系下是错误的。