分享丨【算法题单】贪心算法（基本贪心策略/反悔/区间/字典序/数学/思维/构造）

灵茶山艾府

225817

发布于浙江

堆贪心脑筋急转弯数学字符串排序 C C++Java Python Python3 周赛数据结构数据结构与算法双周赛堆（优先队列）力扣竞赛学习分享

贪心题单贪心题目力扣贪心题单 leetcode贪心 greedy 灵茶山艾府灵神灵神题单

有时候，很难一眼看出一道题是贪心还是 DP。

前言

为方便大家练习，我把比较套路的贪心题目放在前面，更灵活的思维题和构造题放在后面。每个小节的题目均按照从易到难的顺序排列。

如果做题时没有思路，推荐看看本文第五章的「思考清单」。

一、贪心策略

有两种基本贪心策略：

从最小/最大开始贪心，优先考虑最小/最大的数，从小到大/从大到小贪心。在此基础上，衍生出了反悔贪心。
从最左/最右开始贪心，思考第一个数/最后一个数的贪心策略，把 $n$ 个数的原问题转换成 $n - 1$ 个数（或更少）的子问题。

贪心题目的代码往往比较简单，重点是如何证明贪心算法的正确性。

§1.1 从最小/最大开始贪心

优先考虑最小/最大的数，从小到大/从大到小贪心。

如果答案与数组元素顺序无关，一般需要排序。排序后，可以遍历计算。

思维扩展：

§1.2 单序列配对

同上，从最小/最大的元素开始贪心。

§1.3 双序列配对

同上，从最小/最大的元素开始贪心。

§1.4 从最左/最右开始贪心

对于无法排序的题目，尝试从左到右/从右到左贪心。思考第一个数/最后一个数的贪心策略，把 $n$ 个数的原问题转换成 $n - 1$ 个数（或更少）的子问题。

读者可以对比下面的题目和动态规划题单中的线性 DP、状态机 DP 的区别，思考什么情况下只能 DP 不能贪心，从而加深对「局部最优」和「全局最优」的理解。

另见本题单的「§3.1 字典序最小/最大」。

§1.5 划分型贪心

把数组/字符串划分成满足要求的若干段，最小化/最大化划分的段数。

思考方法同上，尝试从左到右/从右到左贪心。

读者可以对比下面的题目和动态规划题单中的划分型 DP 的区别，思考什么情况下只能 DP 不能贪心，从而加深对「局部最优」和「全局最优」的理解。

§1.6 先枚举，再贪心

枚举题目的其中一个变量，将其视作已知条件，然后在此基础上贪心。

也可以枚举答案，检查是否可以满足要求。（类似二分答案）

2171. 拿出最少数目的魔法豆 1748
3085. 成为 K 特殊字符串需要删除的最少字符数 1765
1727. 重新排列后的最大子矩阵 1927 可以优化到 $O (mn)$ 时间
2749. 得到整数零需要执行的最少操作数 2132
2910. 合法分组的最少组数 2132
2234. 花园的最大总美丽值 2562

§1.7 交换论证法

交换论证法（exchange argument）常用于证明一类贪心算法的正确性，也可以用来启发思考。做法如下：

对于题目，猜想按照「某种顺序」处理数据，可以得到最优解。
交换顺序中的两个元素 $a_{i}$ 和 $a_{j}$ ，计算交换后的答案。
对比交换前后的答案。如果交换后，答案没有变得更优，则说明猜想成立。

也可以不用猜想，而是计算「先 $a_{i}$ 后 $a_{j}$ 」和「先 $a_{j}$ 后 $a_{i}$ 」对应的答案，通过比较两个答案谁更优，来确定按照何种顺序处理数据。

讲解（以 2895 题为例）

思维扩展：

相似题目：

2412. 完成所有交易的初始最少钱数 2092

§1.8 相邻不同

以下问题，设 $n$ 是数组 $a$ 的长度， $m$ 是出现次数最多的元素的出现次数。

问题一：给定数组 $a$ ，能否重新排列其中的元素，使得所有相邻元素均不同？如果能，输出重排后的数组。

答：如果 $m \leq n - m + 1$ ，则可以做到，否则无法做到。

问题二：给定数组 $a$ ，每次操作，删除 $a$ 中的两个不同元素。最多能操作多少次？

答：最多操作 $min (⌊ \frac{n}{2} ⌋, n - m)$ 次。

问题三：给定数组 $a$ ，每次操作，删除 $a$ 中的至多两个不同元素。删除所有元素，最少要操作多少次？

答：最少操作 $max (⌈ \frac{n}{2} ⌉, m)$ 次。

证明+具体操作方案

2335. 装满杯子需要的最短总时长 1360
3659. 数组元素分组 1440
1753. 移除石子的最大得分 1488 同 2335 题，但数据范围更大
767. 重构字符串 1681
1054. 距离相等的条形码 1702 同 767 题
2856. 删除数对后的最小数组长度 1750 有 $O (lo g n)$ 做法
1953. 你可以工作的最大周数 1804
3785. 避免禁用值的最小交换次数 2052
3664. 两个字母卡牌游戏 2158
3495. 使数组元素都变为零的最少操作次数 2206 有 $O (1)$ 公式
3139. 使数组中所有元素相等的最小开销 2666
621. 任务调度器相同元素至少间隔 n
358. K 距离间隔重排字符串（会员题）

思维扩展：

§1.9 反悔贪心

一般要用到堆。

讲解

LCP 30. 魔塔游戏约 1900
1642. 可以到达的最远建筑 1962
630. 课程表 III 约 2000
871. 最低加油次数 2074
3362. 零数组变换 III 2424 虽然没有反悔的过程，但思路和 871 是类似的
2813. 子序列最大优雅度 2582 也可以不用堆
3049. 标记所有下标的最早秒数 II 3111
3711. 不出现负余额的最大交易额（会员题）
2599. 使前缀和数组非负（会员题）

二、区间贪心

区间贪心有如下经典问题：

不相交区间（单机器调度/活动安排）：给定一些区间，从中选出尽量多的两两互不相交的区间。
区间分组（任务调度/会议室）：给定一些区间，把这些区间分成最少的组，使得每组内的区间互不相交。
区间选点（射气球，Interval Stabbing）：给定一些区间，在数轴上放置最少的点，使得每个区间都包含至少一个点。最少要放置多少个点？
区间覆盖（灌溉花园）：给定一些区间，从中选出尽量少的区间，覆盖一条指定线段 $[s, t]$ 。

一般来说，区间合并问题（2.5 节）是按左端点排序，其余大多数区间贪心是按右端点排序。请读者在做题后，仔细体会为什么要这样排序。

§2.1 不相交区间

变形：每个区间有各自的分数，从中选一些两两互不相交的区间，最大化得分之和。详见动态规划题单的「§7.2 不相交区间」。

§2.2 区间分组

2406. 将区间分为最少组数 1713
253. 会议室 II（会员题）

§2.3 区间选点

本质上和不相交区间是一样的。

§2.4 区间覆盖

图解

§2.5 合并区间

可能算不上贪心，但为了题单的完整性，也放到这个分类中。

§2.6 其他区间贪心

三、字符串贪心

§3.1 字典序最小/最大

字典序的定义如下：

对于两个字符串 $a$ 和 $b$ ，从左到右依次比较字符 $a [i]$ 和 $b [i]$ 的 ASCII 值的大小。
$a [i] \neq = b [i]$ 时，如果 $a [i] < b [i]$ ，那么 $a$ 的字典序更小，否则 $b$ 的字典序更小。
如果没有出现 $a [i] \neq = b [i]$ ，则短的字符串字典序更小。
如果两个字符串的长度和内容均相同，那么两个字符串的字典序一样。

字典序的定义也可以推广到数组上，按照上述方法比较两个数组的字典序。

倒序贪心：

另见单调栈题单的「四、最小字典序」。

§3.2 回文串贪心

部分题目也出现在其他贪心分类中，为了题单的完整性整理到一起。

另见数学题单的「§7.1 回文数」。

§3.3 合法括号字符串

见数据结构题单中的「§3.4 合法括号字符串」。

四、数学贪心

§4.1 基础

§4.2 乘积贪心

§4.3 排序不等式

给定两个长度均为 $n$ 的数组 $a$ 和 $b$ ，可以交换同一数组内的元素，最小化/最大化

a [0] \cdot b [0] + a [1] \cdot b [1] + \dots + a [n - 1] \cdot b [n - 1]

把 $a$ 和 $b$ 都从小到大排序，可以最大化上式。

把 $a$ 从小到大排序， $b$ 从大到小排序，可以最小化上式。

思维扩展：

2561. 重排水果 2222 基于 $min$ 的排序不等式
3547. 图中边值的最大和链/环

§4.4 均值不等式

栅栏问题：长为 $n$ 米的篱笆栅栏，围成一个矩形，矩形面积最大是多少？

变形：长为 $n$ 米的栅栏分成 $k$ 份，每份围成一个正方形，面积之和最小是多少？

§4.5 中位数贪心

给定数组 $nums$ ，每次操作可以把其中一个数加一或者减一。把 $nums$ 的所有数都变成一样的，最少要操作多少次？

把所有数都变成 $nums$ 的中位数是最优的。

证明

思维扩展：环形问题

3937. 使数组变为模交替数组的最少操作次数 I 做到 $O (n lo g n)$

§4.6 归纳法

§4.7 其他数学贪心

五、思维题

回想一下高考数学的最后一题，三个小问，前两小问让你计算一些特殊情况，第三小问让你计算/证明一个一般的结论。这其实就是从特殊到一般的思考方式，我们在做算法题（尤其是思维题和构造题）时，也可以从最简单、最特殊的情况开始，去探索题目的性质，逐渐过渡到一般情况。

思考清单

小型数组： $nums$ 只有 $1$ 个数？只有 $2$ 个数？只有 $3$ 个数？
万里挑一： $nums$ 所有数都相同？只有一个数不一样？有两个数不一样？某个数特别大？
黑白世界：只有两种数？例如 $[0, 1, 0, 1, 0, 1]$ 或者 $ababab$ 。
反向思考：如果答案是 $1$ ，输入会是什么样的？如果答案是 $2$ ？是 $nums [0]$ ？是 $nums [1]$ ？
枚举归纳：试试小范围打表，暴力枚举所有情况，找规律。

思考这些特殊情况，有时会产生求解原问题的灵感。

§5.1 从特殊到一般

2745. 构造最长的新字符串 1607 想一想 $z = 0$ 怎么做， $z = 1$ 怎么做， $z = 2$ 怎么做
2611. 老鼠和奶酪 1663 想一想 $k = 1$ 怎么做， $k = 2$ 怎么做
1029. 两地调度同 2611 题
2645. 构造有效字符串的最少插入数考虑 $word$ 长为 $2$ 的所有情况，以及答案等于 $1$ 的情况
2202. K 次操作后最大化顶端元素 1717
2568. 最小无法得到的或值 1754
1702. 修改后的最大二进制字符串 1825
3012. 通过操作使数组长度最小 1833
2350. 不可能得到的最短骰子序列 1961
3660. 跳跃游戏 IX 2187
517. 超级洗衣机
2499. 让数组不相等的最小总代价 2633
3357. 最小化相邻元素的最大差值 3077
3431. 对数字排序的最小解锁下标（会员题）

§5.2 脑筋急转弯

从一般到特殊。

§5.3 等价转化

§5.4 逆向思维

时光倒流：

§5.5 贡献法

另见单调栈题单的「三、贡献法」。

另见动态规划题单的「§10.2 统计合法元素的价值总和」，这些题有数学做法。

§5.6 两次扫描

从左到右扫一次，再从右到左扫一次。

§5.7 交换元素

为什么同一连通块中的元素可以随意交换？

§5.8 分类讨论

2525. 根据规则将箱子分类 1301
860. 柠檬水找零
2165. 重排数字的最小值 1362
2091. 从数组中移除最大值和最小值 1384
1033. 移动石子直到连续 1421
3876. 构造奇偶一致的数组 II 1444
2918. 数组的最小相等和 1526
2591. 将钱分给最多的儿童 1531
2131. 连接两字母单词得到的最长回文串 1557
3789. 采购的最小花费 1580
2844. 生成特殊数字的最少操作 1588
1247. 交换字符使得字符串相同 1597
838. 推多米诺 1638
2170. 使数组变成交替数组的最少操作数 1663
2202. K 次操作后最大化顶端元素 1717
3922. 使二进制字符串连贯的最少翻转次数 1759
2982. 找出出现至少三次的最长特殊子字符串 II 1773
3724. 转换数组的最少操作次数 1790 变形题见我的题解
3001. 捕获黑皇后需要的最少移动次数 1797
2423. 删除字符使频率相同非暴力做法
2934. 最大化数组末位元素的最少操作次数 1803
3800. 使二进制字符串相等的最小成本 1841
2162. 设置时间的最少代价 1852
3942. 排序排列的最少操作数 1855
3863. 将一个字符串排序的最小操作次数 1860
3440. 重新安排会议得到最多空余时间 II 1998
3886. 可排序整数求和 1999
1927. 求和游戏 2005
2508. 添加边使所有节点度数都为偶数 2060
3240. 最少翻转次数使二进制矩阵回文 II 2080
3854. 使数组奇偶交替的最少操作 2095
3548. 等和矩阵分割 II 2245
2029. 石子游戏 IX 2277
2468. 根据限制分割消息 2382
420. 强密码检验器
3609. 到达目标点的最小移动次数 2419
1040. 移动石子直到连续 II 2456
335. 路径交叉
1330. 翻转子数组得到最大的数组值 2482
3197. 包含所有 1 的最小矩形面积 II 2541
3366. 最小数组和做到 $O (n lo g n)$
2499. 让数组不相等的最小总代价 2633
3311. 构造符合图结构的二维矩阵 2664
3139. 使数组中所有元素相等的最小开销 2666
3017. 按距离统计房屋对数目 II 2709
2983. 回文串重新排列查询 2780
3395. 唯一中间众数子序列 I 2800
3357. 最小化相邻元素的最大差值 3077
1900. 最佳运动员的比拼回合做到 $O (lo g n)$ 或者 $O (1)$
LCP 48. 无限棋局
LCP 21. 追逐游戏

六、构造题

构造题会给定一些约束，我们要构造一个满足这些约束的数组/字符串等。

思考方式和第五章的「思考清单」是一样的，在特殊情况中寻找灵感。

1304. 和为零的 N 个不同整数 1167
3963. 构造恰好一条路径的网格 1311
942. 增减字符串匹配 1444
1968. 构造元素不等于两相邻元素平均值的数组 1499 做法不止一种，见我在官解下的评论
1253. 重构 2 行二进制矩阵 1506
1317. 将整数转换为两个无零整数的和做到 $O (lo g n)$ 。进阶问题：最小化 $a$
3513. 不同 XOR 三元组的数目 I 1663
2182. 构造限制重复的字符串 1680
3592. 硬币面值还原 1701
969. 煎饼排序约 1800
406. 根据身高重建队列
1605. 给定行和列的和求可行矩阵 1868 西北角法
2375. 根据模式串构造最小数字做到 $O (n)$
324. 摆动排序 II 约 2000
3988. 创建一个恰好有 K 条路径的网格图 I 2055
667. 优美的排列 II 约 2100
2122. 还原原数组 2159
1980. 找出不同的二进制字符串做到 $O (n)$
3680. 生成赛程 2378
932. 漂亮数组约 2500
2790. 长度递增组的最大数目 2620
3311. 构造符合图结构的二维矩阵 2664
2573. 找出对应 LCP 矩阵的字符串 2682
1982. 从子集的和还原数组 2872
280. 摆动排序（会员题）
484. 寻找排列（会员题）
3990. 创建一个恰好有 K 条路径的网格图 II（会员题）

更多构造题，可以去 Codeforces 搜索 constructive algorithms。

七、交互题

八、其他

答疑

问：贪心和 DP 的区别是什么？

答：DP 可以视为带记忆化的暴力搜索，只要不遗漏任何分支，答案一定是对的。贪心可以视为带剪枝的搜索，如果贪心策略不对，就容易贪过头，把正确的分支给剪掉。

问：有没有万能方法，判断一道题是贪心还是 DP？

答：很难。如果不知道题目类型，把 DP 想成贪心的大有人在。我的建议是先思考 DP 能不能做，再思考贪心。如果 DP 的时间复杂度足以通过题目，就不用思考贪心策略了。

此外，这也说明按照题单刷题的缺点：提前知道题目类型，跳过了一些思考步骤。如何弥补这个缺点？请看如何科学刷题。

关联题单

数学题单中的「博弈论」。
数据结构题单中的「堆」。
图论题单中的 Dijkstra 算法和 Kruskal/Prim 算法，这些算法都是基于贪心策略一的，即优先选最小的数。

算法题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。