Typescript-Algorithms
    Preparing search index...

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

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

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

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

    有两种基本贪心策略：

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

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

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

    思维扩展：

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

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

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

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

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

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

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

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

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

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

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

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

    讲解（以 2895 题为例）

    思维扩展：

    相似题目：

    给定正整数数组，每次操作，把数组中的两个数各减少一，并去掉变成 0 的数。目标：使最后剩下的数最小，或者最大化操作次数。

    由于每次操作的都是两个下标不同的数，把这些下标按顺序拼接，可以构造出一个相邻元素不同的序列。例如 (1,2),(2,3),(3,4) 这三个操作，可以拼接成 [1,2,3,2,3,4]。

    证明

    输出具体构造

    扩展：

    一般要用到堆。

    讲解

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

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

    任务：总结上述四种区间贪心问题的解法，尤其是排序的规则和理由，什么时候要按照左端点排序？什么时候要按照右端点排序？排序的目的是什么？欢迎在评论区分享你的总结笔记。

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

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

    图解

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

    字典序的定义如下：

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

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

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

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

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

    a[0]⋅b[0]+a[1]⋅b[1]+⋯+a[n−1]⋅b[n−1]

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

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

    思维扩展：

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

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

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

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

    两种证明方法

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

    思考清单

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

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

    从一般到特殊。

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

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

    如果想做更多思维题和构造题，可以去 Codeforces 看看。

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

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

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

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

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

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

    如何科学刷题？

    1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
    2. 二分查找（二分答案/最小化最大值/最大化最小值/第K小）
    3. 单调栈（基础/矩形面积/贡献法/最小字典序）
    4. 网格图（DFS/BFS/综合应用）
    5. 位运算（基础/性质/拆位/试填/恒等式/思维）
    6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
    7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
    8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
    9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
    10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
    11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
    12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

    我的题解精选（已分类）

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

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

    Settings

    Member Visibility

    On This Page

    前言一、贪心策略二、区间贪心三、字符串贪心四、数学贪心五、思维题六、构造题七、其他答疑关联题单算法题单