企业官网建设流程全解析

提起“贪心算法”，很多人第一反应是“每次选最优不就行了”，但真上手刷题的时候，往往会被一道题教做人。最近我在复习算法的时候，把一道编号为437的贪心题反复做了几遍，感触挺深，趁着思路还热乎，把整个过程拆开揉碎了记录一下，也顺便聊聊贪心算法到底该怎么学、怎么用、怎么不翻车。

这篇文章的核心围绕“437贪心”展开——以一道典型的贪心算法实战题为主线，梳理贪心策略的推导过程、代码实现细节、常见反例和调试技巧。无论你是刚开始接触算法的新手，还是刷题遇到瓶颈想补一补贪心这块的老手，这篇都能给你一些参考。

1. 先认清贪心算法：它不是“哪个好选哪个”那么简单

1.1 贪心的本质是“局部最优推导全局最优”

我去过不少算法交流群，发现大家对贪心算法的误解主要集中在一点：觉得贪心就是“每一小步都挑当前看起来最好的选择”。这个说法不算错，但远远不够。

贪心算法真正的核心是局部最优策略能够推导出全局最优解。也就是说，你在每一步做的选择，不仅要能让你当前这一步看起来最好，还得保证做完所有步之后，整体结果也是最优的。这个性质在算法领域叫“贪心选择性质”和“最优子结构”。如果题目不具备这两个性质，你用贪心做出来的答案大概率是错的。

为了说明白这件事，我拿生活中最常见的例子来类比。你去超市买东西，手里有一张满100减20的优惠券，你挑商品的时候当然是想凑满100块而且尽量不超太多——这就是一个典型的贪心思路。但如果你面对的问题是“用最少张数的优惠券覆盖购物车里的所有商品”，那局部最优（每张券都尽量选贵的东西）就可能出问题，因为商品之间有组合关系，你这一张选爽了，后面反而凑不满。

这个例子说明：贪心的边界感非常重要。它只适用于满足贪心选择性质的问题，而不是所有优化问题的万能钥匙。

1.2 什么时候敢用贪心？两个判断条件

我在实际刷题中的经验是，判断一道题能不能用贪心，关键看两件事。

第一，能不能把一个大问题拆成一系列独立的小决策。而且每次小决策之间是互不影响的，做完这个选择之后，后续选择的规模和剩余资源要能清晰地缩小。如果每一步做完之后，剩下的问题和原来问题结构完全一致，只是规模变小了，那贪心通常是有戏的。

第二，局部最优解能不能直接成为全局最优解的一部分。这个条件比较抽象，我的实操判断方式是：先随便拿几个小规模数据手算一遍，看看“每一步都取局部最优”的结果是不是恰好等于全局最优。如果前几个例子算出来都成立，再试试构造反例，构造不出来，才考虑用贪心去解。

这里有一个非常容易踩的思维误区：你把“动态规划”和“贪心”搞混。动态规划也是把大问题拆成小问题，但动态规划会记录每个状态的所有可能取值，最后综合判断；贪心则只保留当前状态下的一个最优走向。可以这样理解，动态规划是“把所有路都走一遍再挑最短的”，贪心是“每条路口只看最顺眼的那条，走进去就不回头”。

判断方法也很简单：如果你发现决策过程需要回头看之前的决策，甚至要撤销重来，那贪心基本不适合。但如果每一步选完，前面的旧选择永远不会被推翻，那就是贪心的舒适区。

2. “437贪心”到底在做什么：一道删数问题的实战拆解

2.1 删数问题：题目描述与直觉

我反复做了好几遍的这道“437贪心”，核心场景是经典的删数问题。题目要求大致是：给定一个由数字组成的字符串（比如"1432219"），要求删除其中k个数字，使得剩下的数字组成的数尽可能小。不能改变数字的相对顺序，k不会超过字符串长度。

第一次看到这个题，很多人的本能想法是：把最大的那几个数字依次删掉不就行了？表面上听起来很有道理，毕竟数字越小越好，而所谓“小”不就是让高位数字尽量小么？但实际操作之后你会发现，这个直觉在大多数时候是错的。

举个例子你就明白了。字符串"1432219"，k=3。如果单纯删掉最大的数字，那就是先把9删了，再删两个7？等一下，这个数字串里没有7。那就删9和两个4？等等，两个4删完，剩下的数是"13221"，这个结果明显不如另一个方案：“删掉4、4、2”，得到"1219”。为什么？因为高位数字的权重远大于低位数字，删掉了中间某一位，后面数字会自动前移补位，所以你要优化的不仅是“删掉哪些位”，更重要的是“删掉之后哪些数字会补到高位来”。

这个问题的本质是：从高位往低位看，只要发现当前位比下一位大，就应该果断删掉当前位。因为当前位留着会让整个数膨胀，删掉它，更小的数字就能补上来。

2.2 删数问题的贪心策略推导

顺着上面的思路，可以整理出删数问题的标准贪心策略：从左往右遍历数字串，维护一个单调递增的栈。每来一个新数字，如果栈顶元素比这个新数字大，而且我们还有剩余删除次数，那就把栈顶弹出去，相当于把“大的高位”删掉，让“小的低位”提前上台。然后新数字入栈。如果遍历完了删除次数还没用完，就直接从末尾删掉多余的数字，因为此时整个数字串已经是递增的，尾部的数字是最大的，删掉它们才能让结果最小。

你可能会好奇：为什么是“单调递增栈”，而不是“单调递减”或者别的什么结构？因为对于一个数字来说，从左到右每一位都应该尽可能小，也就是说高位数字不应该大于低位数字。如果你从左往右看的时候发现某一位比后一位大，就说明这一位是一个“逆序”点，它比后面那位大，把这一位删掉，整体值肯定变小。单调递增栈就是不断纠正这种逆序点的工具。

这个策略其实包含了一个很重要的推论：删除次数足够多的时候，剩下的一定是按位递增的数字串。因为所有逆序点都已经被纠正了。这种情况下，最小的数就是所有剩余数字从左到右升序排列的那个数。

为了更直观，我拿"1432219"，k=3演示一遍：

• 初始化空栈，剩余删除次数r=3。
• 读取第一个字符'1'，栈为空，直接入栈，栈：[1]。
• 读取'4'，栈顶是1，1<4，不删，4入栈，栈：[1,4]。
• 读取'3'，栈顶4>3，删掉4，r=2，此时栈：[1]，继续比较栈顶1<3，3入栈，栈：[1,3]。
• 读取'2'，栈顶3>2，删掉3，r=1，继续比较栈顶1<2，2入栈，栈：[1,2]。
• 读取'2'，栈顶2不大于2，2入栈，栈：[1,2,2]。
• 读取'1'，栈顶2>1，删掉2，r=0，栈：[1,2]，然后1入栈，栈：[1,2,1]。
• 读取'9'，栈顶1<9，9入栈，栈：[1,2,1,9]。
• 遍历结束，r=0，不再额外删除。

输出栈内内容"1219"，这个就是答案。你看，整个过程非常流畅，每一步都在做“看得见的好处”——删掉一个比后一位大的高位数字。

这就是贪心算法的典型节奏：没有回头路，没有全局扫描，只是在一次遍历中持续做局部修正。复杂度当然是O(n)，每一个字符最多进栈出栈各一次，线性时间解决。

2.3 为什么维护一个单调栈而不是每次扫描删最大

看到这里，你可能会产生一个疑问：能不能退一步做暴力方案，每一轮扫描一遍字符串，找到一个最大的数字删掉，重复k轮？这个思路实现起来非常直白，而且小数据量下也能得到正确答案，所以很多人一开始会这么做。

但一旦数据规模上来，问题就暴露了。假设字符串长度n=10万，k=5万，每一轮扫描O(n)，总共O(n*k)就是50亿次操作，这个量级再强的机器也扛不住。更关键的是，每轮“删最大”的全局扫描思维并不符合贪心的决策模式，它只是在蛮力枚举，并且结果往往还不是最优的。

我举个例子给你看看差别。字符串"231"，k=1。按“删最大数字”的思路，最大数字是3，删掉得"21"。但正确的贪心应该是，从左往右发现2>3，应该删2，得到"31"吗？不对，再仔细想，这里比较的是当前位和下一位：2比3小，不删；继续，3比1大，删3，得到"21"，所以"21"反而是对的。不好意思，我换个例子："132"，k=1。删最大思路删3，得到"12"；正确贪心从左往右扫描，1<3不删，3>2删3，得到"12"，这个例子两者一致。

再看一个两者不同的例子："1890"，k=1。删最大思路：最大数字是9，删掉得"180"。贪心扫描：1<8不删，8<9不删，9>0删9，得"180"。还是一致。那到底什么时候不一致？比如"140"，k=1，删最大思路删4，得"10"，扫描法发现1<4不删，4>0删4，得"10"，还是一致。我再想想……其实“删最大数字”在很多小例子上碰巧和贪心结果一致，但它有一个非常严重的缺陷：它只顾数字的大小，没看数字所在的位置。高位的8和低位的9，你删哪个对整个数的影响更大？永远是高位那个。而“删最大数字”不分位置，这在某些构造数据下就会翻车。

比如"2910"，k=1。删最大数字是9，得"210"。但正确贪心是扫描：2<9不删，9>1删9，得"210"。还是一致。我之前想找反例，但突然意识到一个问题：从左往右第一次出现逆序的位置，其左边那个数一定是第一个“比后一位大”的数，这个数不一定是全局最大。删这个高位逆序数，比删全局最大但位置靠后的数更优。比如"1820"，k=1：全局最大数字是8，删8得"120"。但贪心扫描：1<8不删，8>2删8，结果也是"120"。反例要构造的是“全局最大数不在逆序位置”的情况，比如"9182"，全局最大9在最前面，而且9>1是逆序，删9得"182"？贪心扫描同样删9，一致。但如果最大数字出现在已经递增的序列末尾呢？比如"1289"，k=1，全局最大9在末尾，删9得"128"。贪心扫描：1<2不删，2<8不删，8<9不删，没有逆序点，遍历结束删除次数没用完，按规则删末尾最大数，也是删9。结果又一致。

我在推导这个区别的时候发现，“删最大数字”之所以经常碰巧正确，是因为全局最大数字要么处在逆序点，要么处在末尾，而这两个位置恰好也是贪心算法会删的位置。只有一种情况会翻车：全局最大数字既不在末尾，左边又恰好比它小、右边也比它小，此时删它会保留一个高位更大的数字，反而亏了。举个例子："1598"，k=1。全局最大数字是9，位置在倒数第二，删9得"158"。但是贪心扫描：1<5不删，5<9不删，9>8删9，结果还是"158"。我再构造："1596"，k=1，最大数字9在倒数第二，删9得"156"。贪心扫描：1<5不删，5<9不删，9>6删9，得"156"。还是不翻车。看来要翻车，得让全局最大数字右边比它小、并且它的左边也满足升序，同时还有一个“更靠左的高位逆序点”没有被删，但因为k只有1，两个点只能选一个。比如"2719"，k=1，全局最大数字9在末尾？不算。全局最大是9，删9得"271"。但如果k=1，贪心扫描：2<7不删，7>1删7，得"219"。这下就有区别了！"271"和"219"哪个更小？219更小。所以“删最大数字”策略在"2719"，k=1这个问题上给出了错误答案。

这个例子充分说明，用位置感知的贪心策略才是正解，单纯看数字大小不靠谱。单调栈的作用就是始终让当前位置的比较主导决策，而不是全局数字的绝对值主导。

所以删数问题最优解法就是一趟扫描加一个栈，空间O(n)，时间O(n)。这也是为什么我特别建议你把这个题作为贪心的入门实战题——它没有复杂的数学推导，代码也不长，但对“贪心到底贪在哪里”的理解非常到位。

3. 代码实现与参数选择的完整记录

3.1 用 Python 实现删数问题的贪心解法

我实际写这道题的时候，先试过暴力法，写完测试用例之后立刻放弃了。真的，数据量稍微大一点就慢得离谱。换成单调栈版本之后，代码干净了不少。

我用 Python 实现的核心代码大概是这样的：

def remove_k_digits(num: str, k: int) -> str: stack = [] remain = k for ch in num: while stack and remain > 0 and stack[-1] > ch: stack.pop() remain -= 1 stack.append(ch) # 如果删除次数还没用完，说明已经递增，删末尾 if remain > 0: stack = stack[:-remain] if remain < len(stack) else [] # 去掉前导零 res = ''.join(stack).lstrip('0') return res if res else '0'

几个关键点我展开说一下。

首先是while 循环的触发条件。很多初学者写这道题时会写成if stack and stack[-1] > ch，这是错误的。因为删掉一个栈顶之后，可能新的栈顶仍然比当前字符大，需要连续删，只有用 while 才能把一个位置产生的所有逆序全部清理干净。比如"54321"，k=2，遍历到'3'的时候，栈里有[5,4]，4>3删4，剩下5还大于3，还要再删5，必须 while 一直删到栈顶不大于当前字符或者删除次数用完为止。

其次是前导零的处理。删除数字之后，字符串开头可能出现'0'，比如"10200"，k=1，正确结果是"200"而不是"0200"，因为整数的最前面不能有0。用lstrip('0')把开头的零全部去掉，如果最后全删完变成空串，要返回"0"而不是空字符串。这个细节很容易被忽略，我在本地跑测试的时候，就因为这个前导零的问题和预期结果不一致，排查了好一阵。

最后是剩余删除次数的处理。遍历完成后，如果整个数字串已经严格递增，那么任何逆序点都没有了，此时再删除的话，应该删末尾最大数字，因为末尾数字的权重最小。代码里的stack[:-remain]就是在做这件事。注意如果remain大于等于当前栈长度，意味着所有数字都要被删掉，直接返回"0"。

3.2 边界条件：k 为 0、前导零、删不满怎么办

边界条件是这道题最容易丢分的地方，我把常见的几个场景都整理成了一张表。

这几个用例在提交之前一定要自己测一遍。尤其是 "10200"，很多方案算出来是"0200"，然后被判错，其实不是算法思维的错，是字符串处理和边界判断的锅。

还有一个小细节，k 可能为 0。这种情况下直接返回原始字符串就好，如果代码里remain > 0的判断写成了while remain:或者if remain:，其实也还好，但如果忘了处理前导零，就会把"10200"变成"10200"的情况误删成"10200"，没问题，说明没影响。对于k为0，我的建议是直接加一个早退判断：

if k == 0: return num

这样既省时，也能避免误操作。

3.3 测试用例设计与结果验证

写完代码之后，我一直习惯用几组精心设计过的测试用例来验证，而不是随便跑一两个用例就收工。对于删数问题，我重点做三件事。

第一，验证基础正确性。拿"1432219"，k=3这种已知答案的用例跑，看输出是不是"1219"。这个用例来自 LeetCode 的官方示例，答案可靠，可以直接作为基准。

第二，验证边界条件。把上面的表格逐行跑一遍，确保前导零、全删光、删除次数不足这些场景都正确。

第三，暴力法对比验证。写一个递归或者组合数枚举的暴力解法，生成随机的小规模数字串和随机k，把贪心结果和暴力结果对比。这个方法在刷题阶段特别有用，能快速发现贪心策略的隐藏bug。我用到的主要是 Python 的itertools.combinations，枚举所有删除组合，找到最小值，再和贪心结果比对。

import itertools def brute_force(num: str, k: int) -> str: n = len(num) min_val = None for comb in itertools.combinations(range(n), n - k): s = ''.join(num[i] for i in comb).lstrip('0') s = s if s else '0' if min_val is None or int(s) < int(min_val): min_val = s return min_val

随机测了一百组小数据之后，贪心算法输出的结果和暴力结果完全一致，我这才算真正放下心来。这里有一个经验：算法题的正确性，用随机暴力对拍验证是最可靠的，比你手推十个例子都有用。

4. 贪心算法真正容易翻车的场景

4.1 贪心失效的经典反例

聊完删数问题这道“正面教材”，我得给你兜兜底，说说贪心算法在什么情况下会翻车。很多人刷题刷到“贪心”标签的时候觉得什么题都能贪，结果一提交就错，其实是因为没有区分题目是否具备贪心选择性质。

最经典的反例就是找零钱问题。假设你有面值为1、5、11的硬币，要凑出15块钱，最少用几枚。按贪心的思路，每次选不超过剩余金额的最大面值硬币，11+1+1+1+1共5枚。但正确答案其实是5+5+5共3枚。你发现问题在哪？贪心选择“当前最大面值硬币”，局部最优并没有导向全局最优，因为11这个面值浪费了太多余额，导致后续需要一堆1块钱来凑。

另一个经典反例是部分背包问题和0-1背包问题的对比。如果物品可以分割，贪心按单位重量价值排序是有效的，因为你能取一部分；但如果是0-1背包，也就是物品只能整件装包，贪心按单位价值排序就可能出错——一个单位价值低但重量轻、总价值高的组合可能反而更优。

这些反例说明一个重要问题：贪心算法成立与否，不是看问题“像不像贪心”，而是要从数学上证明局部最优能推出全局最优。如果你不想做复杂证明，至少要养成构造反例的习惯，构造不出来再用。

4.2 如何判断动态规划还是贪心

做题的时候，最让新手头疼的抉择就是：这道题到底用贪心还是动态规划？

我个人的经验法是先画决策树。从初始状态开始，逐步画出每一种选择的分支。如果某个节点后续的所有最优路径都不依赖于之前怎么选的，只依赖于当前剩余状态，那动态规划和贪心都能用，此时贪心更快；如果某个节点的后续走向需要“记住”之前的选择细节，那只能动态规划。

举一个生活中的例子。你去旅行，要在有限天数里最大化游览景点数量，景点之间的交通时间是固定的。这个问题看似可以用贪心——每天挑最近的景点去。但如果景点之间有复杂的路线依赖，比如去B景点必须路过A，那么你的每个选择都会影响后面的可达路径，这种场景贪心就会失效，要用动态规划记录每个景点的访问状态。

刷题时的实操建议：先看看题目数据范围。如果n在10到20之间，大概率是状态压缩动态规划或者搜索；如果n在10万级别，贪心和动态规划都有可能，此时看看每一步选择是否“后效”。所谓后效，就是这次的选择会不会影响后续决策的评估标准。有后效用动态规划，无后用贪心。

4.3 实战中总结出的几条经验

刷了这几年算法题，我在贪心这块总结了几条经验，不一定写进教科书，但实战中非常有用。

第一条经验：贪心算法想证明正确性，可以先尝试“交换论证法”。具体做法是假设最优解和贪心解不一致，找出第一个分歧的位置，然后证明把最优解的这一步换成贪心的选择，不会让答案变差。如果可以成功交换，贪心策略就是正确的。删数问题就可以这样证明：如果某个最优方案删的不是第一个逆序点，那么换成删逆序点，结果不会更差。

第二条经验：很多贪心题的本质是排序加一次遍历。比如会议室安排、任务调度、区间覆盖这一类，往往只需要对输入按某个关键字排序，然后线性扫描一遍就能出结果。如果你看到一个题需要反复比较和调整，那大概率不是贪心。

第三条经验：误差用反例测试兜底。哪怕你已经信心满满证明了一遍贪心正确，在提交之前也要构造几组数据跑一下。反例构造的思路通常是让贪心选择的“短期优势”和“长期代价”发生冲突，比如找零钱问题里的11元硬币，短期让你少用一枚硬币，长期却因为剩余金额不规整要用掉大量小面额硬币。

5. 常见问题与调试技巧实录

5.1 常见报错与排查思路

我把做这道题以及其他贪心题的过程中，最常见的几类问题整理成了表格，你在实战中遇到类似报错，可以直接对照排查。

重点提醒一下最后一行的整数溢出问题。题目给出的数字串可能长达几十万位，直接转成 Python 的 int 虽然理论上不溢出，但性能会非常差，而且 Python 的 int 和字符串之间反复比较大小，远不如直接比较字符 ASCII 码高效。我在实现里全程没有调用 int，只比较字符大小，因为数字字符的字典序和数值序是一致的，'0'<'1'<'2'<...<'9'。这个技巧很多人没注意到，但它是这类大数题目的通用优化手段。

5.2 小技巧：用随机数据对比验证贪心

我在前面提到过暴力法对比验证，这里展开说说具体怎么操作，因为这是我自己调试时最喜欢的利器。

写一个验证函数，生成随机长度的小规模数字串，随机k值，然后把贪心结果和暴力结果做比较。Python 的random模块可以直接用来生成字符串，但为了可复现，我通常还会加上随机种子。

import random import itertools def test_random(trials=1000): for _ in range(trials): n = random.randint(1, 8) num = ''.join(str(random.randint(0, 9)) for _ in range(n)) k = random.randint(0, n) ans1 = remove_k_digits(num, k) ans2 = brute_force(num, k) if ans1 != ans2: print("错误:", num, k, ans1, ans2) return print("全部通过")

为什么这个做法有效？因为暴力法的时间复杂度是组合级别，只能跑小数据，但小数据已经足够验证贪心策略的每一步是否正确。你连续测几百组随机用例，如果全部输出一致，基本可以认为这个算法对任意数据都正确。这是我个人非常推荐的一个测试习惯，不只是贪心题，其他算法题写完之后，也可以写一个暴力对拍器来验证。

有一个需要注意的点：随机生成的数字串里会出现大量前导零。比如生成"0012"，删除k个数字后，去掉了前导零可能变成"0"或"1"之类。暴力法里我特意做了lstrip('0')和空串处理，就是为了让两种算法的输出口径一致。对拍脚本最怕的就是“算法一样，输出格式不一样”，这种问题查起来非常容易怀疑人生。

5.3 关于“437”这个编号我的一点记录习惯

写到这里，简单聊一下“437”这个编号。这其实不是题目本身的编号，而是我自己刷题文件里的一个编号习惯。我的项目文件都是按照难度+序号来命名的，比如“437贪心”就是我当时做到的第437个算法练习，主题是贪心。这个编号方式帮我快速定位和复盘每一类题型，也让我养成了一个习惯：每完成一类算法题，在命名时就把核心标签写上去。

后来我发现这个习惯挺适合推荐给正在刷题的朋友。你不用把文件名起得多花哨，用“序号+算法类型”就够了，比如“437贪心”“438动态规划”“439回溯”。当题目积累到几百道的时候，你再回头翻文件夹，就能很清晰地看到自己在哪些算法类型上练得多、哪些练得少。我整理这篇博文的时候，也顺手统计了一下自己文件夹里的分布，发现贪心相关的题目数量其实不多，但每一道的思路都很有代表性。

这个编号习惯的另一个好处是方便写复盘笔记。每做完一道题，我会在这个文件里追加一段几行字的思路总结，比如“这道题用单调栈维护递增序列”“反例：找零钱不能用贪心”之类的提炼。等到下次面试或者带项目的时候，这些碎片化的记录就是你最宝贵的知识库。

从“437贪心”这一条记录出发，我不仅复习了删数问题的标准解法，还想明白了贪心和动态规划的边界、暴力对拍验证的价值、以及一套属于自己的刷题文件组织方式。我个人实际做下来最深的体会是：贪心算法不是靠“感觉”选出来的，而是靠“反证+对拍”练出来的。下次再遇到一个看着可以贪心的题目，先别急着写代码，拿笔在纸上画出第一个逆序点，想清楚每一步为什么不会回头，再动键盘也不迟。