1. 贪心算法一种“短视”却高效的解题哲学在解决算法问题时我们常常面临一个抉择是追求全局最优的完美解还是接受一个“足够好”的局部最优解贪心算法Greedy Algorithm就是后者最典型的代表。它不像动态规划那样瞻前顾后也不像回溯法那样反复试错而是像一个目光坚定的决策者在每一步都做出当下看起来最好的选择并且永不回头。这种“短视”的策略听起来似乎不够聪明但在许多特定问题上它却能以惊人的效率找到全局最优解或者一个非常接近最优的可行解。我第一次深入理解贪心算法是在解决一个经典的“活动选择问题”时。面对一堆时间可能冲突的活动如何安排才能参加最多的活动如果去穷举所有排列组合计算量是指数级的。而贪心策略告诉我每次都选择结束时间最早的那个活动。这个简单的规则背后蕴含着对问题结构的深刻洞察——结束早的活动能为后续活动留出更多时间。最终我仅用一次排序和一次遍历就解决了问题代码简洁效率极高。从那以后我对这种“以简驭繁”的算法思想产生了浓厚的兴趣。贪心算法并不复杂但用好它却需要技巧。它并非万能钥匙其有效性高度依赖于问题是否具有“贪心选择性质”和“最优子结构”。简单来说就是局部最优的选择是否能最终导向全局最优并且大问题的最优解包含其子问题的最优解。这篇文章我将结合自己踩过的坑和实战经验为你彻底拆解贪心算法。无论你是正在准备技术面试的求职者还是希望优化程序性能的开发者理解贪心算法都能让你在面对某些问题时拥有一种降维打击的解题思路。我们将从核心思想入手剖析其适用场景并通过多个经典案例的代码实现与变体分析让你真正掌握这门“短视”的艺术。2. 贪心算法的核心思想与适用条件解析贪心算法的核心思想可以概括为“步步为营只争朝夕”。它把解决问题的过程看作是一系列步骤在每一个步骤中都依据某个“贪心准则”Greedy Criterion做出一个局部最优的选择。一旦做出选择就不再改变也不会回溯去考虑其他可能性。整个算法的框架通常是自顶向下的先做出当前最优选择然后将剩下的问题规约成一个更小的子问题并重复这个过程。2.1 贪心算法的两大基石贪心选择性质与最优子结构贪心算法能正确工作的前提是问题必须满足两个关键性质。这是判断一个问题能否用贪心法求解的黄金标准也是面试中经常被考察的重点。贪心选择性质Greedy Choice Property这个性质是说我们可以通过做出局部最优贪心的选择来构造全局最优解。换句话说在每一步我们不需要考虑未来只需要选择当前看起来最好的选项这个选择最终会被包含在某个全局最优解中。这是贪心算法区别于动态规划的核心动态规划每一步的选择依赖于子问题的解而贪心算法则直接做出一个当时看来最好的选择。例如在“找零钱”问题中假设硬币体系是{1, 5, 10, 25}美分要凑出36美分。贪心策略是每次选择面值不超过剩余金额的最大硬币。第一步选25美分剩余11美分第二步选10美分剩余1美分第三步选1美分。最终解是[25, 10, 1]。这个策略之所以有效是因为在这个特定的硬币体系下局部最优选最大可能硬币能导向全局最优硬币总数最少。但请注意如果硬币体系是{1, 3, 4}要凑出6美分贪心策略4, 1, 1用了3枚硬币而最优解其实是两个3美分硬币。这就说明了贪心选择性质不是天然成立的。最优子结构Optimal Substructure这个性质是指一个问题的最优解包含其子问题的最优解。如果我们做出了第一步的贪心选择后剩下的问题子问题和原问题具有相同的形式并且原问题的最优解可以由这个贪心选择加上子问题的最优解构成那么该问题就具有最优子结构。继续以活动选择问题为例。假设我们按照结束时间排序后第一次贪心地选择了活动A1结束最早。那么剩下的问题就变成了在所有与A1不冲突的活动中即开始时间晚于A1结束时间的活动再安排尽可能多的活动。原问题“安排最多活动”的最优解必然包含“在选定A1后从剩余兼容活动中安排最多活动”这个子问题的最优解。这个性质保证了我们可以安全地应用贪心策略并且能通过递归或迭代的方式求解。注意证明一个问题满足这两个性质尤其是贪心选择性质是应用贪心算法的难点和关键。很多时候需要严谨的数学归纳法或反证法。在实际编程和面试中对于经典问题如霍夫曼编码、最小生成树我们可以直接应用已知的贪心策略对于新问题则需要仔细分析并尝试证明或者通过举反例来验证策略是否有效。2.2 贪心算法的典型工作流程与框架一个典型的贪心算法实现通常遵循以下步骤这个框架有助于我们在面对新问题时进行思考问题转化将原始问题建模为一系列待做出的选择。确定贪心准则找出一个度量标准用于在每一步评价所有候选选择并选出“最好”的一个。这个准则通常是排序的依据比如“价值最大”、“成本最小”、“结束时间最早”等。排序如果需要根据贪心准则对所有候选元素进行排序。这是许多贪心算法预处理的关键一步。迭代选择遍历排序后的列表对于每个元素判断其是否满足加入当前解的约束条件如不冲突、资源足够等。如果满足则将其加入解集并更新问题的状态如剩余资源、时间点等。构造解迭代完成后收集到的选择序列就构成了算法给出的解。下面是一个高度抽象化的贪心算法伪代码框架它适用于一大类“选择问题”def greedy_algorithm(items): # 1. 根据贪心准则对物品进行排序 sorted_items sort(items, keygreedy_criterion) solution [] # 用于存放最终的解 current_state initialize_state() # 初始化问题状态如剩余容量、当前时间等 # 2. 迭代选择 for item in sorted_items: if is_feasible(item, current_state): # 判断当前选择是否可行 solution.append(item) # 加入解集 update_state(current_state, item) # 更新状态 return solution这个框架非常通用。例如在背包问题分数背包中items是物品greedy_criterion是单位重量价值is_feasible检查是否还能装下update_state减少剩余容量。在活动选择问题中items是活动greedy_criterion是结束时间is_feasible检查是否与已选活动时间冲突update_state更新最后一个活动的结束时间。3. 贪心算法经典案例深度剖析与代码实现理解理论最好的方式就是实践。让我们通过几个最经典、面试最高频的贪心算法问题来深入感受其魅力与实现细节。我会提供清晰的代码并附上关键注释和复杂度分析。3.1 案例一活动选择问题问题描述给定一组活动每个活动有开始时间start[i]和结束时间end[i]。同一时间只能进行一个活动。如何选择活动使得能参加的活动数量最多贪心策略每次选择结束时间最早的活动这样能给后续活动留下尽可能多的时间。代码实现Pythondef activity_selection(start, end): 解决活动选择问题 :param start: 活动开始时间列表 :param end: 活动结束时间列表 :return: 选择的活动索引列表 # 将活动组合成元组开始时间结束时间索引并按结束时间排序 activities list(zip(start, end, range(len(start)))) activities.sort(keylambda x: x[1]) # 按结束时间升序排序 selected [] last_end_time -float(inf) # 初始化上一个选中活动的结束时间 for s, e, idx in activities: if s last_end_time: # 如果当前活动开始时间不早于上一个活动的结束时间 selected.append(idx) last_end_time e # 更新最后结束时间 return selected # 示例 start_times [1, 3, 0, 5, 8, 5] end_times [2, 4, 6, 7, 9, 9] result activity_selection(start_times, end_times) print(f选择的活动索引从0开始: {result}) print(f最大活动数量: {len(result)}) # 输出选择的活动索引: [0, 1, 3, 4] (对应活动(1,2), (3,4), (5,7), (8,9))复杂度分析时间复杂度O(n log n)主要开销在于对活动按结束时间排序。之后的遍历是O(n)。空间复杂度O(n)用于存储排序后的活动列表和结果列表如果不算输出空间则为O(1)。实操心得排序是关键务必确保是按照结束时间排序而不是开始时间。按开始时间排序的贪心策略是无效的很容易举出反例。边界处理初始化last_end_time为负无穷确保第一个活动结束时间最早的那个一定能被选中。也可以直接选中排序后的第一个活动然后从第二个开始遍历。变体思考如果活动有权重即价值要求总价值最大贪心算法就不再适用结束早的不一定价值高这通常需要用到动态规划。3.2 案例二分数背包问题问题描述有N件物品和一个容量为C的背包。第i件物品的重量是weight[i]价值是value[i]。你可以拿走物品的一部分即可分割。如何装包使得背包中物品的总价值最大贪心策略计算每件物品的单位重量价值价值/重量每次优先拿取单位价值最高的物品直到拿完该物品或背包装满。代码实现Pythondef fractional_knapsack(values, weights, capacity): 解决分数背包问题 :param values: 物品价值列表 :param weights: 物品重量列表 :param capacity: 背包总容量 :return: 最大总价值 # 计算单位价值并排序 items [] for i in range(len(values)): unit_value values[i] / weights[i] items.append((unit_value, weights[i], values[i], i)) items.sort(reverseTrue, keylambda x: x[0]) # 按单位价值降序排列 total_value 0.0 remaining_capacity capacity for unit_val, weight, val, idx in items: if remaining_capacity weight: # 可以拿完整件物品 total_value val remaining_capacity - weight print(f拿取物品{idx}的全部重量{weight}价值{val}) else: # 只能拿一部分 fraction remaining_capacity / weight value_taken val * fraction total_value value_taken print(f拿取物品{idx}的{fraction:.2f}部分重量{remaining_capacity}价值{value_taken:.2f}) break # 背包已满 return total_value # 示例 values [60, 100, 120] weights [10, 20, 30] capacity 50 max_value fractional_knapsack(values, weights, capacity) print(f\n背包能获得的最大总价值为: {max_value:.2f})复杂度分析时间复杂度O(n log n)主要开销在于按单位价值排序。空间复杂度O(n)用于存储物品信息列表。注意事项与0-1背包的区别这是贪心算法能取得最优解的前提——物品可以分割。对于经典的0-1背包物品不可分割贪心算法无法保证最优必须使用动态规划。这是一个非常重要的考点。精度问题计算单位价值时使用浮点数。在最终输出总价值时根据题目要求决定保留小数位数。3.3 案例三霍夫曼编码问题描述给定一组字符及其出现频率设计一种二进制前缀码使得编码后的总长度最短。前缀码意味着任何一个字符的编码都不是另一个字符编码的前缀。贪心策略反复将频率最低的两棵二叉树合并直到只剩一棵树。这棵树的叶子节点就是字符从根到叶子的路径就是该字符的编码左0右1或自定义。代码实现Python——使用最小堆优先队列import heapq from collections import defaultdict class HuffmanNode: def __init__(self, char, freq): self.char char # 字符叶子节点有值内部节点为None self.freq freq # 频率 self.left None self.right None # 定义比较运算符用于堆排序按频率 def __lt__(self, other): return self.freq other.freq def build_huffman_tree(char_freq): 构建霍夫曼树 :param char_freq: 字典字符-频率 :return: 霍夫曼树的根节点 # 初始化最小堆 min_heap [] for char, freq in char_freq.items(): node HuffmanNode(char, freq) heapq.heappush(min_heap, node) # 合并节点直到堆中只剩一个节点 while len(min_heap) 1: # 弹出两个频率最小的节点 left_node heapq.heappop(min_heap) right_node heapq.heappop(min_heap) # 创建新的内部节点频率为两者之和 merged_freq left_node.freq right_node.freq merged_node HuffmanNode(None, merged_freq) merged_node.left left_node merged_node.right right_node # 将新节点推回堆中 heapq.heappush(min_heap, merged_node) # 堆中剩下的唯一节点就是根节点 return heapq.heappop(min_heap) if min_heap else None def generate_codes(root, current_code, code_dictNone): 从霍夫曼树生成编码字典递归 if code_dict is None: code_dict {} if root is None: return # 如果是叶子节点存储编码 if root.char is not None: code_dict[root.char] current_code else: # 遍历左子树和右子树 generate_codes(root.left, current_code 0, code_dict) generate_codes(root.right, current_code 1, code_dict) return code_dict def huffman_encoding(char_freq): 霍夫曼编码主函数 :return: (编码字典, 霍夫曼树根节点) root build_huffman_tree(char_freq) huffman_codes generate_codes(root) return huffman_codes, root # 示例 frequency {a: 5, b: 9, c: 12, d: 13, e: 16, f: 45} codes, tree_root huffman_encoding(frequency) print(字符霍夫曼编码) for char, code in sorted(codes.items()): print(f {char}: {code}) # 计算平均编码长度和总长度 total_chars sum(frequency.values()) avg_length sum(freq * len(codes[char]) for char, freq in frequency.items()) / total_chars print(f\n平均编码长度: {avg_length:.2f} bits)复杂度分析时间复杂度O(n log n)。每次堆操作插入、弹出最小值是O(log n)需要进行n-1次合并操作。空间复杂度O(n)用于存储堆和树节点。核心要点为什么贪心有效频率低的字符放在树的深处编码长频率高的字符放在浅处编码短这自然减少了整体加权路径长度。每次合并最小的两棵树保证了全局的优化。数据结构选择使用最小堆Python的heapq来高效地获取频率最小的节点这是实现的关键。前缀码特性由于所有字符都是叶子节点保证了没有任何编码是另一个编码的前缀解码时不会产生歧义。3.4 案例四最小生成树之Prim算法问题描述对于一个带权的连通无向图如何找到一个边的子集使得其构成一棵树连接所有顶点并且所有边的权重之和最小Prim算法的贪心策略从任意一个顶点开始逐步“生长”一棵树。在每一步从连接已选顶点集合和未选顶点集合的所有边中选择一条权重最小的边并将该边连接的未选顶点加入已选集合。代码实现Python——使用邻接矩阵和优先队列优化import heapq import sys def prim_algorithm_adjacency_matrix(graph): 使用Prim算法求解最小生成树邻接矩阵表示 :param graph: 二维列表graph[i][j]表示顶点i到j的边权无边则为inf或0视情况 :return: 最小生成树的总权重以及边的列表 (weight, u, v) num_vertices len(graph) # 假设graph是对称矩阵且graph[i][i] 0 visited [False] * num_vertices min_heap [] # (weight, vertex) total_weight 0 mst_edges [] # 用于记录选择的边 # 从顶点0开始 start_vertex 0 heapq.heappush(min_heap, (0, start_vertex, -1)) # (权重, 当前顶点, 来自哪个顶点) while min_heap and len(mst_edges) num_vertices: weight, current_vertex, from_vertex heapq.heappop(min_heap) if visited[current_vertex]: continue # 已经访问过跳过 # 标记为已访问并加入MST visited[current_vertex] True total_weight weight if from_vertex ! -1: # 起始顶点没有“来自”的边 mst_edges.append((weight, from_vertex, current_vertex)) # 查看当前顶点的所有邻居 for neighbor in range(num_vertices): if not visited[neighbor] and graph[current_vertex][neighbor] 0: # 如果邻居未访问且之间有边 edge_weight graph[current_vertex][neighbor] heapq.heappush(min_heap, (edge_weight, neighbor, current_vertex)) # 检查是否所有顶点都被访问图是否连通 if len(mst_edges) ! num_vertices - 1: print(警告图不连通无法生成最小生成树) return None, [] return total_weight, mst_edges # 示例图邻接矩阵 # 顶点: 0-A, 1-B, 2-C, 3-D graph_matrix [ [0, 2, 0, 6], # A: 连接B(2), D(6) [2, 0, 3, 8], # B: 连接A(2), C(3), D(8) [0, 3, 0, 0], # C: 连接B(3) [6, 8, 0, 0] # D: 连接A(6), B(8) ] total_weight, edges prim_algorithm_adjacency_matrix(graph_matrix) if total_weight is not None: print(f最小生成树总权重: {total_weight}) print(选择的边权重顶点1顶点2:) for w, u, v in edges: print(f {w}: {u} - {v})复杂度分析使用邻接矩阵和二叉堆时间复杂度O(V²)其中V是顶点数。因为我们需要对每个顶点遍历所有其他顶点来查找最小边。使用邻接表和斐波那契堆可以优化到O(E V log V)但二叉堆实现如本例通常是O(E log V)在稠密图中接近O(V² log V)。空间复杂度O(V)用于存储访问标记、优先队列等。与Kruskal算法的对比 Prim算法是“加点法”从一个顶点出发扩展。而Kruskal算法是“加边法”对所有边排序后从小到大选择不构成环的边加入。两者都是贪心算法但策略不同。Prim算法在稠密图上效率更高而Kruskal在稀疏图上更简单易实现。实操心得图连通性检查Prim算法要求图是连通的。实现时最后检查生成的边数是否为V-1如果不是则说明图不连通无法形成生成树。优先队列的使用使用堆来高效获取连接已选集合和未选集合的最小权边是算法效率的关键。我们存储的是(weight, vertex, from_vertex)。避免重复添加在弹出堆顶元素时必须检查该顶点是否已被访问visited因为同一个顶点可能被以不同权重多次加入堆中。4. 贪心算法的局限性、证明方法与实战技巧贪心算法并非银弹。它的高效性建立在问题满足特定性质的基础上。盲目套用贪心策略很可能得到错误答案。4.1 何时贪心会失效——经典反例剖析理解贪心算法的局限性和掌握其应用场景同等重要。下面是一些经典的反例0-1背包问题问题物品不可分割。物品重量[10, 20, 30]价值[60, 100, 120]背包容量50。贪心策略单位价值单位价值为[6, 5, 4]。先拿物品0价值60重10再拿物品1价值100重20此时总重30价值160。剩余容量20无法装下物品2。最终价值160。最优解拿物品1和物品2总重50价值220。贪心策略失败了。硬币找零问题非标准体系问题硬币面额[1, 3, 4]需要凑出总金额6。贪心策略每次选最大面额先拿4剩余2再拿1剩余1再拿1。共3枚硬币[4,1,1]。最优解两枚3元硬币[3,3]。贪心策略再次失败。最短路径问题带负权边问题求单源最短路径但图中存在负权边。贪心策略Dijkstra算法Dijkstra算法是贪心的它假设“当前最短路径就是最终最短路径”。但在负权边存在时这个假设不成立因为未来可能通过一条负权边让路径变得更短。Dijkstra算法会得出错误结果此时需要使用能处理负权边的Bellman-Ford算法。这些反例告诉我们在应用贪心算法前必须尝试证明或至少举不出反例。对于面试或竞赛如果问题描述符合经典贪心模型如区间调度、分数背包、霍夫曼编码可以大胆使用。如果是新问题则需要谨慎分析。4.2 如何证明贪心算法的正确性证明贪心算法正确性的常用方法有以下几种掌握它们有助于你在面对新问题时进行推理交换论证法这是最常用、最直观的方法。思路是假设存在一个最优解O我们的贪心解是G。尝试通过一步步“交换”O中的元素将其转变为G同时保证解不会变差或变得更好。如果能完成这种转换就证明了G至少和O一样好即G也是最优解。举例活动选择问题。假设最优解O的第一个活动不是结束最早的活动A1。那么我们可以把O中的第一个活动换成A1由于A1结束最早这个替换不会造成新的冲突且活动数不变。因此存在一个以A1开始的最优解。这证明了第一步贪心选择是安全的。然后对剩余活动递归应用此论证。归纳法归纳基础证明对于规模最小的问题例如只有一个活动时贪心算法能产生最优解。归纳步骤假设对于所有规模小于k的问题贪心算法都能产生最优解。证明对于规模为k的问题做出贪心选择后剩下的子问题规模小于k根据归纳假设贪心算法能给出子问题的最优解。再结合贪心选择性质原问题的最优解由贪心选择加上子问题最优解构成。拟阵理论这是一套更形式化、更强大的数学工具。如果一个组合优化问题可以建模成一个拟阵那么贪心算法一定能找到最优解。许多经典问题如最小生成树、任务调度都可以用拟阵来描述。但这属于更高级的理论一般面试中不会要求。对于大多数工程和面试场景掌握交换论证法并能够清晰表述思路就足够了。关键是说明“做出贪心选择后剩下的问题仍然保持最优子结构并且这个选择包含在某个最优解中”。4.3 贪心算法在面试与竞赛中的实战技巧识别贪心模式看到以下关键词或场景要优先考虑贪心“最多/最少”、“最大/最小”、“最短/最长”。涉及“选择”、“安排”、“调度”、“分配”的问题。问题可以分解为一系列步骤且每一步的选择似乎很直观。经典问题的变体如区间问题按起点或终点排序、背包问题分数背包、调度问题最短作业优先、贪心匹配等。从排序入手超过一半的贪心算法题目第一步都是对数据进行某种排序按时间、权重、比例、坐标等。排序是贪心策略的“准备工作”它让“当前最优选择”变得显而易见。举反例验证如果你设计了一个贪心策略但不确定是否正确最快的方法是尝试构造一个反例。想一个小的、特别的测试用例看看你的策略是否会产出明显非最优的结果。这是面试中快速检验思路的好方法。与动态规划对比思考当一个问题既像可以用贪心又感觉可能需要动态规划时思考两者的区别贪心做出选择后不可撤销。子问题通常是唯一的做出选择后剩下什么就是什么。动态规划需要记录并比较多种可能的选择。子问题有重叠需要保存中间结果。一个简单的判断如果问题要求“所有”或“计数”通常需要DP如果只要求“一个”最优解且具有明显的贪心性质可以尝试贪心。代码模板化很多贪心问题的代码结构相似。熟练掌握本章第2节给出的通用框架以及几个经典案例的代码能让你在实现时快速无误。5. 贪心算法常见问题与排查技巧实录在实际编码和调试贪心算法时会遇到一些典型问题。这里我总结了一份“避坑指南”都是我在刷题和项目中真实踩过的坑。5.1 问题排查清单问题现象可能原因排查与解决方法结果不是最优解1. 问题本身不满足贪心选择性质。2. 排序的“贪心准则”选错了。3. 约束条件判断is_feasible有误。1.首要步骤用小的、边缘的测试用例验证。构造反例。2. 重新审视问题尝试证明贪心性质。如果无法证明考虑动态规划或回溯。3. 检查排序依据是按开始时间、结束时间、比值还是其他多尝试几种排序方式。4. 仔细检查可行性判断逻辑特别是边界条件如还是。程序陷入死循环或结果异常1. 状态更新update_state逻辑错误导致条件永远满足或永不满足。2. 循环终止条件不正确。1. 添加打印语句输出每次循环的current_state和候选item观察状态变化是否符合预期。2. 检查循环条件确保在解已找到或资源耗尽时能正确退出。算法复杂度超出预期1. 使用了低效的数据结构如列表查找代替集合/堆。2. 在循环内进行了不必要的重复操作如重复排序。1.使用合适的数据结构需要快速获取最小/最大值用堆heapq需要快速查找存在性用集合set需要按键排序和查找用有序字典collections.OrderedDict或TreeMap。2. 确保排序等预处理只在循环外做一次。处理浮点数导致精度问题在分数背包、比例计算等问题中使用浮点数比较。1. 尽量避免直接比较浮点数是否相等。使用一个极小的误差范围epsilon如abs(a - b) 1e-9。2. 如果可能将所有计算转化为整数运算。例如在分数背包中可以先不除比较value1 * weight2和value2 * weight1。多条件排序时优先级混乱需要按多个关键字排序但顺序写反。明确多个排序条件的优先级。Python中sorted(list, keylambda x: (x[0], -x[1]))表示先按第一项升序再按第二项降序。想清楚哪个条件是主要的贪心准则。5.2 独家避坑技巧与心得从暴力法思考当完全没思路时先想想暴力解法枚举所有可能。然后观察在暴力解法的决策树上是否每一步都有一个“明显更好”的选择这个“明显更好”的选择标准往往就是贪心准则。例如安排会议暴力法是枚举所有子集。观察发现如果一个会议结束得早它给后面留出的时间就多这暗示了按结束时间排序的贪心策略。画图辅助对于区间问题、调度问题在纸上画出时间轴和区间直观地感受哪种排序方式能放下更多区间。对于图论问题画出小规模的图手动模拟Prim或Dijkstra算法的执行过程。视觉化能极大帮助理解。测试用例设计不要只测常规用例。务必测试以下情况边界用例空输入、单个元素、所有元素都相同、极端大的值。导致贪心失效的用例回忆那些经典反例构造类似的数据测试你的算法。随机生成与暴力对比对于规模小的问题n20可以写一个暴力枚举最优解的程序用大量随机数据运行你的贪心算法对比结果是否一致。这是验证算法正确性的强力手段。理解库函数的时间复杂度Python的sort()是O(n log n)heapq.heappush/pop是O(log n)。如果你在循环内部调用这些函数总复杂度可能会变成O(n² log n)之类。确保它们只在必要的地方被调用。贪心算法的“近似”角色对于NP难问题如旅行商问题TSP贪心算法如最近邻算法可以作为启发式方法快速得到一个近似解虽然不保证最优但结果往往可以接受。在工程中这是一种在时间和解的质量之间取得平衡的常用策略。这时向面试官说明你使用贪心是出于对效率的考虑并知道它的局限性会显得你思考全面。贪心算法是一种将复杂问题简单化的艺术。它教会我们有时候不必追求绝对的全局最优一个基于局部信息的、高效的、足够好的决策往往是工程实践中最务实的选择。掌握它不仅能让你在算法面试中游刃有余更能培养一种“抓主要矛盾”的解决问题思维。下次当你遇到一个看似复杂的选择问题时不妨先问问自己“如果我只考虑眼前这一步最好的选择是什么这个选择会不会让未来的路越走越窄”如果答案是否定的那么贪心或许就是那把钥匙。
