作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/g6KTKL/
一、贪心策略
有两种基本贪心策略：
从最小/最大开始贪心，优先考虑最小/最大的数，从小到大/从大到小贪心。在此基础上，衍生出了反悔贪心。
从最左/最右开始贪心，思考第一个数/最后一个数的贪心策略，
把 n 个数的原问题转换成 n−1 个数（或更少）的子问题。
§1.1 从最小/最大开始贪心
优先考虑最小/最大的数，从小到大/从大到小贪心。
如果答案与数组元素顺序无关，一般需要排序。排序后，可以遍历计算。
1833. 雪糕的最大数量 1253
3074. 重新分装苹果 ~1260
2279. 装满石头的背包的最大数量 ~1260
1005. K 次取反后最大化的数组和 1275
1481. 不同整数的最少数目 1284
1403. 非递增顺序的最小子序列 1288
3010. 将数组分成最小总代价的子数组 I 1292
1338. 数组大小减半 1303
1710. 卡车上的最大单元数 1310
3075. 幸福值最大化的选择方案 1326
2554. 从一个范围内选择最多整数 I 1333
2126. 摧毁小行星 1335
2587. 重排数组以得到最大前缀分数 1337
976. 三角形的最大周长 1341
1846. 减小和重新排列数组后的最大元素 1454
945. 使数组唯一的最小增量 1448
1647. 字符频次唯一的最小删除次数 1510
2971. 找到最大周长的多边形 1521
2178. 拆分成最多数目的正偶数之和 1538
2567. 修改两个元素的最小分数 1609
1509. 三次操作后最大值与最小值的最小差 1653
LCP 40. 心算挑战 和下面这题一起做
1262. 可被三整除的最大和 1762
948. 令牌放置 1762
1775. 通过最少操作次数使数组的和相等 1850
2333. 最小差值平方和 2011
2412. 完成所有交易的初始最少钱数 2092
910. 最小差值 II 2135
2835. 使子序列的和等于目标的最少操作次数 2207
1196. 最多可以买到的苹果数量（会员题）
2214. 通关游戏所需的最低生命值（会员题）
2098. 长度为 K 的最大偶数和子序列（会员题）同 LCP 40
2548. 填满背包的最大价格（会员题）
3119. 最大数量的可修复坑洼（会员题）
2557. 从一个范围内选择最多整数 II（会员题）
§1.2 单序列配对
同上，从最小/最大的元素开始贪心。
2144. 打折购买糖果的最小开销 1261
561. 数组拆分 ~1300
1877. 数组中最大数对和的最小值 1301
881. 救生艇 1530 经典题
2592. 最大化数组的伟大值 1569 田忌赛马
2576. 求出最多标记下标 1843
§1.3 双序列配对
同上，从最小/最大的元素开始贪心。
2037. 使每位学生都有座位的最少移动次数 1357
455. 分发饼干 ~1380
2410. 运动员和训练师的最大匹配数 1381
1433. 检查一个字符串是否可以打破另一个字符串 1436
870. 优势洗牌 1648 田忌赛马
826. 安排工作以达到最大收益 1709
2449. 使数组相似的最少操作次数 2076
1889. 装包裹的最小浪费空间 2214
2561. 重排水果 2222
2323. 完成所有工作的最短时间 II（会员题）
§1.4 从最左/最右开始贪心
对于无法排序的题目，尝试从左到右/从右到左贪心。思考第一个数/最后一个数的贪心策略，
把 n 个数的原问题转换成 n−1 个数（或更少）的子问题。
读者可以对比下面的题目和 动态规划题单 中的线性 DP、状态机 DP 的区别，思考什么情况下只能 DP 不能贪心，从而加深对「局部最优」和「全局最优」的理解。
3191. 使二进制数组全部等于 1 的最少操作次数 I 1312
1827. 最少操作使数组递增 1315
2027. 转换字符串的最少操作次数 1346
605. 种花问题 ~1400
3111. 覆盖所有点的最少矩形数目 1401
2957. 消除相邻近似相等字符 1430
3192. 使二进制数组全部等于 1 的最少操作次数 II 1433
2789. 合并后数组中的最大元素 1485
1529. 最少的后缀翻转次数 同 3192 题
1144. 递减元素使数组呈锯齿状 1559
2086. 喂食仓鼠的最小食物桶数 1623
2571. 将整数减少到零需要的最少操作数 1649
3228. 将 1 移动到末尾的最大操作次数 ~1650
2712. 使所有字符相等的最小成本 1791
1536. 排布二进制网格的最少交换次数 1881
2673. 使二叉树所有路径值相等的最小代价 1917
861. 翻转矩阵后的得分 ~2000
955. 删列造序 II ~2000
2366. 将数组排序的最少替换次数 2060
2193. 得到回文串的最少操作次数 2091
2528. 最大化城市的最小电量 2236
2422. 使用合并操作将数组转换为回文序列（会员题）
§1.5 划分型贪心
把数组/字符串划分成满足要求的若干段，最小化/最大化划分的段数。
思考方法同上，尝试从左到右/从右到左贪心。
读者可以对比下面的题目和 动态规划题单 中的划分型 DP 的区别，思考什么情况下只能 DP 不能贪心，从而加深对「局部最优」和「全局最优」的理解。
1221. 分割平衡字符串 1220
2405. 子字符串的最优划分 1355
2294. 划分数组使最大差为 K 1416
2358. 分组的最大数量 1503
2522. 将字符串分割成值不超过 K 的子字符串 1605
1546. 和为目标值且不重叠的非空子数组的最大数目 1855
2436. 使子数组最大公约数大于一的最小分割数（会员题）
2892. 将相邻元素相乘后得到最小化数组（会员题）
§1.6 先枚举，再贪心
枚举题目的其中一个变量，将其视作已知条件，然后在此基础上贪心。
也可以枚举答案，检查是否可以满足要求。（类似二分答案）
1007. 行相等的最少多米诺旋转 1541
2171. 拿出最少数目的魔法豆 1748
3085. 成为 K 特殊字符串需要删除的最少字符数 1765
1727. 重新排列后的最大子矩阵 1927 结合 2171 题思考
2749. 得到整数零需要执行的最少操作数 2132
2910. 合法分组的最少组数 2132
2234. 花园的最大总美丽值 2562
§1.7 交换论证法
交换论证法（exchange argument）用于证明一类贪心算法的正确性，也可以用来启发思考。做法如下：
对于题目，猜想按照「某种顺序」处理数据，可以得到最优解。
交换顺序中的两个元素 ai和 aj，计算交换后的答案。
对比交换前后的答案。如果交换后，答案没有变得更优，则说明猜想成立。
注：也可以不用猜想，而是计算「先 ai 后 aj 」和「先 aj后ai」对应的答案，通过比较两个答案谁更优，来确定按照何种顺序处理数据。
讲解（以 2895 题为例）
2895. 最小处理时间 1352
3219. 切蛋糕的最小总开销 II 1789
1665. 完成所有任务的最少初始能量 1901
2136. 全部开花的最早一天 2033
注：该方法也可以用来证明一些配对问题的贪心算法，例如 2449. 使数组相似的最少操作次数。
§1.8 相邻不同
给定正整数数组，每次操作，把数组中的两个数各减少一，并去掉变成
0
0 的数。目标：使最后剩下的数最小，或者最大化操作次数。
由于每次操作的都是两个下标不同的数，把这些下标按顺序拼接，可以构造出一个相邻元素不同的序列。例如
(1,2),(2,3),(3,4) 这三个操作，可以拼接成 [1,2,3,2,3,4]。
证明/构造方案
2335. 装满杯子需要的最短总时长 1360
1753. 移除石子的最大得分 1488 同 2335 题，数据范围更大
1054. 距离相等的条形码 1702
2856. 删除数对后的最小数组长度 1750 有 O(logn) 做法
1953. 你可以工作的最大周数 1804
767. 重构字符串 ~1900
3139. 使数组中所有元素相等的最小开销 2666
621. 任务调度器 相同元素至少间隔 n
358. K 距离间隔重排字符串（会员题）
扩展：
984. 不含 AAA 或 BBB 的字符串
1405. 最长快乐字符串 1821
§1.9 反悔贪心
一般要用到堆。
讲解
LCP 30. 魔塔游戏 ~1900
1642. 可以到达的最远建筑 1962
630. 课程表 III ~2000
871. 最低加油次数 2074
2813. 子序列最大优雅度 2582 也可以不用堆
3049. 标记所有下标的最早秒数 II 3111
2463. 最小移动总距离 做到 O((n+m)log(n+m))
2599. 使前缀和数组非负（会员题）
注：在网络流中，寻找增广路的过程也是一种反悔贪心。
二、区间贪心
区间贪心有如下经典问题：
不相交区间（单机器调度/活动安排）：给定一些区间，从中选出尽量多的两两互不相交的区间。
区间分组（任务调度/会议室）：给定一些区间，把这些区间分成最少的组，使得每组内的区间互不相交。
区间选点（射气球）：给定一些区间，在数轴上放置最少的点，使得每个区间都包含至少一个点。
区间覆盖（灌溉花园）：给定一些区间，从中选出尽量少的区间，覆盖一条指定线段
[s,t]。
任务：总结上述四种区间贪心问题的解法，尤其是排序的规则和理由，什么时候要按照左端点排序？什么时候要按照右端点排序？排序的目的是什么？欢迎在评论区分享你的总结笔记。
§2.1 不相交区间
646. 最长数对链 ~1700
435. 无重叠区间 ~1750
1520. 最多的不重叠子字符串 2363
变形：每个区间有各自的分数，从中选一些两两互不相交的区间，最大化得分之和。详见 动态规划题单 中的「§6.4 不相交区间」。
§2.2 区间分组
2406. 将区间分为最少组数 1713
253. 会议室 II（会员题）
§2.3 区间选点
452. 用最少数量的箭引爆气球 ~1700
757. 设置交集大小至少为2 2379
§2.4 区间覆盖
图解
45. 跳跃游戏 II ~1700
1024. 视频拼接 1746
1326. 灌溉花园的最少水龙头数目 1885
§2.5 合并区间
可能算不上贪心，但为了题单的完整性，也放到这个分类中。
56. 合并区间
57. 插入区间
55. 跳跃游戏
763. 划分字母区间 1443
3169. 无需开会的工作日 1483
2580. 统计将重叠区间合并成组的方案数 1632
2963. 统计好分割方案的数目 1985
2584. 分割数组使乘积互质 2159
616. 给字符串添加加粗标签（会员题）
758. 字符串中的加粗单词（会员题）
759. 员工空闲时间（会员题）
2655. 寻找最大长度的未覆盖区间（会员题）
§2.6 其他区间贪心
1288. 删除被覆盖区间 非暴力做法
2054. 两个最好的不重叠活动 1883
1705. 吃苹果的最大数目 1930
1353. 最多可以参加的会议数目 2016
2589. 完成所有任务的最少时间 2381
三、字符串贪心
§3.1 字典序最小/最大
字典序的定义如下：
对于两个字符串 a 和 b，从左到右依次比较
a[i] 和 b[i] 的字符 ASCII 值的大小。
a[i] ≠ b[i] 时，如果
a[i]<b[i]，那么
a 的字典序更小，否则
b 的字典序更小。
如果没有出现
a[i] != b[i]，则短的字符串字典序更小。
如果两个字符串的长度和内容均相同，那么两个字符串的字典序一样。
字典序的定义也可以推广到数组上，按照上述方法比较两个数组的字典序。
1323. 6 和 9 组成的最大数字 1194
3216. 交换后字典序最小的字符串 1243
2697. 字典序最小回文串 1304
1881. 插入后的最大值 1381
2734. 执行子串操作后的字典序最小字符串 1405
1946. 子字符串突变后可能得到的最大整数 1445
1663. 具有给定数值的最小字符串 1461
1328. 破坏回文串 1474
2259. 移除指定数字得到的最大结果 非暴力做法
2566. 替换一个数字后的最大差值 非暴力做法
670. 最大交换 非暴力做法
3106. 满足距离约束且字典序最小的字符串 1515
1053. 交换一次的先前排列 1633
2375. 根据模式串构造最小数字 1642
2182. 构造限制重复的字符串 1680
738. 单调递增的数字 ~1700
3170. 删除星号以后字典序最小的字符串 1772
1363. 形成三的最大倍数 1823
1754. 构造字典序最大的合并字符串 1829
1202. 交换字符串中的元素 1855
2434. 使用机器人打印字典序最小的字符串 1953
2948. 交换得到字典序最小的数组 2047
564. 寻找最近的回文数
1505. 最多 K 次交换相邻数位后得到的最小整数 2337
2663. 字典序最小的美丽字符串 2416
555. 分割连接字符串（会员题）
3088. 使字符串反回文（会员题）
§3.2 回文串贪心
部分题目也出现在其他贪心分类中，为了题单的完整性整理到一起。
409. 最长回文串 ~1250
2697. 字典序最小回文串 1304
680. 验证回文串 II ~1400
1328. 破坏回文串 1474
1400. 构造 K 个回文字符串 1530
2131. 连接两字母单词得到的最长回文串 1557
2384. 最大回文数字 1636
3035. 回文字符串的最大数量 1857
1616. 分割两个字符串得到回文串 1868
1147. 段式回文 1912
2193. 得到回文串的最少操作次数 2091
564. 寻找最近的回文数
266. 回文排列（会员题）
2422. 使用合并操作将数组转换为回文序列（会员题）
1842. 下个由相同数字构成的回文串（会员题）
3088. 使字符串反回文（会员题）
四、数学贪心
§4.1 基础
2160. 拆分数位后四位数字的最小和 1314
2578. 最小和分割 1351
2244. 完成所有任务需要的最少轮数 1372
2870. 使数组为空的最少操作次数 1392
1217. 玩筹码 1408
LCS 01. 下载插件
3091. 执行操作使数据元素之和大于等于 K 1522
397. 整数替换
§4.2 乘积贪心
628. 三个数的最大乘积
1567. 乘积为正数的最长子数组长度 1710
§4.3 排序不等式
给定两个长度均为 n 的数组 a 和 b，可以交换同一数组内的元素，最小化/最大化
a[0]⋅b[0]+a[1]⋅b[1]+⋯+a[n−1]⋅b[n−1]
把 a 和 b 都从小到大排序，可以最大化上式。
把 a 从小到大排序，b 从大到小排序，可以最小化上式。
2285. 道路的最大总重要性 1496
3016. 输入单词需要的最少按键次数 II 1534
1402. 做菜顺序 1679
2931. 购买物品的最大开销 1822
1589. 所有排列中的最大和 1871
1874. 两个数组的最小乘积和（会员题）
2268. 最少按键次数（会员题）同 3016 题
§4.4 基本不等式
栅栏问题：长为 n 米的篱笆栅栏，围成一个矩形，矩形面积最大是多少？
变形：长为
n 米的栅栏分成 k 份，每份围成一个正方形，面积之和最小是多少？
3081. 替换字符串中的问号使分数最小 1905
1969. 数组元素的最小非零乘积 1967
2939. 最大异或乘积 2128
2897. 对数组执行操作使平方和最大 2301
§4.5 中位数贪心
给定数组，每次操作可以把其中一个数加一/减一，把所有数都变成一样的，最少要操作多少次？
把所有数都变成数组的中位数是最优的。
两种证明方法
462. 最小操作次数使数组元素相等 II
2033. 获取单值网格的最小操作数 1672
2448. 使数组相等的最小开销 2005
2607. 使子数组元素和相等 2071
2967. 使数组成为等数数组的最小代价 2116
1478. 安排邮筒 2190
2968. 执行操作使频率分数最大 2444
1703. 得到连续 K 个 1 的最少相邻交换次数 2467
3086. 拾起 K 个 1 需要的最少行动次数 2673
LCP 24. 数字游戏
296. 最佳的碰头地点（会员题）二维中位数贪心
§4.6 归纳法
2952. 需要添加的硬币的最小数量 1784
330. 按要求补齐数组 同 2952 题
1798. 你能构造出连续值的最大数目 1931
§4.7 其他数学贪心
1414. 和为 K 的最少斐波那契数字数目 1466 难点在证明上
3107. 使数组中位数等于 K 的最少操作数 1605
754. 到达终点数字 ~2000
1058. 最小化舍入误差以满足目标（会员题）
五、思维题
回想一下高考数学的最后一题，三个小问，前两小问让你计算一些特殊情况，第三小问让你计算/证明一个一般的结论。这其实就是从特殊到一般的思考方式，我们在做算法题（尤其是思维题和构造题）时，也可以从最简单、最特殊的情况开始，去探索题目的性质，逐渐过渡到一般情况。
思考清单
小型数组：
nums 只有 1 个数？只有 2 个数？只有 3 个数？
万里挑一：
nums
nums 所有数都相同？只有一个数不一样？有两个数不一样？某个数特别大？
黑白世界：只有两种数？例如
[0,1,0,1,0,1] 或者 ababab。
反向思考：如果答案是 1，输入会是什么样的？如果答案是 2？
是 nums[0]？是 nums[1]？
枚举归纳：试试小范围打表，暴力枚举所有情况，找规律。
思考这些特殊情况，有时会产生求解原问题的灵感。
§5.1 从特殊到一般
2645. 构造有效字符串的最少插入数 1478
2745. 构造最长的新字符串 1607 考虑 x,y,z 其中一个是 0
2611. 老鼠和奶酪 1663
1029. 两地调度 同 2611 题
2202. K 次操作后最大化顶端元素 1717
2568. 最小无法得到的或值 1754
1702. 修改后的最大二进制字符串 1825
3012. 通过操作使数组长度最小 1833
1526. 形成目标数组的子数组最少增加次数 1872
2350. 不可能得到的最短骰子序列 1961
517. 超级洗衣机
2499. 让数组不相等的最小总代价 2633
§5.2 脑筋急转弯
从一般到特殊。
1903. 字符串中的最大奇数 1249
2396. 严格回文的数字 1329
1689. 十-二进制数的最少数目 1355
521. 最长特殊序列 Ⅰ ~1400
3227. 字符串元音游戏 ~1450
2419. 按位与最大的最长子数组 1496
2811. 判断是否能拆分数组 1543
2211. 统计道路上的碰撞次数 1581
3207. 与敌人战斗后的最大分数 1591
2546. 执行逐位运算使字符串相等 1605
1503. 所有蚂蚁掉下来前的最后一刻 1619
1332. 删除回文子序列 1629
1975. 最大方阵和 1648
1145. 二叉树着色游戏 1741
2332. 坐上公交的最晚时间 1841
2680. 最大或值 1912
2731. 移动机器人 1923 联系 1503 题
3125. 使得按位与结果为 0 的最大数字（会员题）
1794. 统计距离最小的子串对个数（会员题）
§5.3 逆向思维
2139. 得到目标值的最少行动次数 1417
1558. 得到目标数组的最少函数调用次数 1637
2718. 查询后矩阵的和 1769 时光倒流
417. 太平洋大西洋水流问题 ~1900
991. 坏了的计算器 1909
2227. 加密解密字符串 1945
§5.4 巧妙转换
2914. 使二进制字符串变美丽的最少修改次数 1480
1657. 确定两个字符串是否接近 1530
2551. 将珠子放入背包中 2042
1585. 检查字符串是否可以通过排序子字符串得到另一个字符串 2333
1040. 移动石子直到连续 II 2456
1183. 矩阵中 1 的最大数量（会员题）
六、构造题
构造题会给定一些约束，我们要构造一个满足这些约束的数组/字符串等。
思考方式和第五章的「思考清单」是一样的，在特殊情况中寻找灵感。
942. 增减字符串匹配 1444
1968. 构造元素不等于两相邻元素平均值的数组 1499 做法不止一种，见我在官解下的 评论
1253. 重构 2 行二进制矩阵 1506
2182. 构造限制重复的字符串 1680
969. 煎饼排序 ~1800
1605. 给定行和列的和求可行矩阵 1868 西北角法
2375. 根据模式串构造最小数字 做到 O(n)
324. 摆动排序 II ~2000
667. 优美的排列 II ~2100
2122. 还原原数组 2159
932. 漂亮数组 ~2500
2573. 找出对应 LCP 矩阵的字符串 2682
1982. 从子集的和还原数组 2872
280. 摆动排序（会员题）
484. 寻找排列（会员题）
如果想做更多思维题和构造题，可以去 Codeforces 看看。
七、其他
2740. 找出分区值 1302
1033. 移动石子直到连续 1421
1864. 构成交替字符串需要的最小交换次数 1601
1899. 合并若干三元组以形成目标三元组 1636
2498. 青蛙过河 II 1759
2311. 小于等于 K 的最长二进制子序列 1840
3002. 移除后集合的最多元素数 1917
659. 分割数组为连续子序列 ~2100
2732. 找到矩阵中的好子集 2240 注意数据范围
2790. 长度递增组的最大数目 2620
782. 变为棋盘
420. 强密码检验器
LCP 26. 导航装置
LCP 70. 沙地治理
2753. 计算一个环形街道上的房屋数量 II（会员题）
答疑
问：贪心和 DP 的区别是什么？
答：DP 可以视为带记忆化的暴力搜索，只要不遗漏任何分支，答案一定是对的。贪心可以视为带剪枝的搜索，如果贪心策略不对，就容易贪过头，把正确的分支给剪掉。
问：有没有万能方法，判断一道题是贪心还是 DP？
答：很难。如果不知道题目类型，把 DP 想成贪心的大有人在。我的建议是先思考 DP 能不能做，再思考贪心。如果 DP 的时间复杂度足以通过题目，就不用思考贪心策略了。
此外，这也说明按照题单刷题的缺点：提前知道题目类型，跳过了一些思考步骤。如何弥补这个缺点？请看 如何科学刷题。