贪心算法
贪心算法
[!info] related notes 算法面试题型 MOC
贪心算法详解
贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致结果是全局最好或最优的算法策略。
基本概念
贪心算法的核心思想是：局部最优导致全局最优。
贪心算法的特点
- 局部最优选择：在每一步都做出当前看起来最佳的选择
- 不可回退：一旦做出选择，就不再改变
- 高效性：通常比其他算法(如动态规划)更高效
- 不保证全局最优：只在某些特定问题中能得到最优解
贪心算法的适用条件
贪心算法适用于满足以下两个条件的问题：
- 贪心选择性质：局部最优选择能导致全局最优解
- 最优子结构：问题的最优解包含其子问题的最优解
贪心算法的基本步骤
- 建立数学模型来描述问题
- 将问题分解为若干个子问题
- 对每个子问题求解，得到局部最优解
- 把子问题的解合并成原问题的一个解
贪心策略
- 从最小/最大开始贪心，优先考虑最小/最大的数，从小到大/从大到小贪心。在此基础上，衍生出了反悔贪心。
- 从最左/最右开始贪心，思考第一个数/最后一个数的贪心策略，把 n 个数的原问题转换成 n−1 个数（或更少）的子问题。
普通贪心
从最小/最大开始贪心
优先考虑最小/最大的数，从小到大/从大到小贪心。
如果答案与数组元素顺序无关，一般需要排序。排序后，可以遍历计算。
单序列配对
双序列配对
从最左/最右开始贪心
对于无法排序的题目，尝试从左到右/从右到左贪心。思考第一个数/最后一个数的贪心策略，把 n 个数的原问题转换成 n−1 个数（或更少）的子问题。
读者可以对比下面的题目和 动态规划题单 中的线性 DP、状态机 DP 的区别，思考什么情况下只能 DP 不能贪心，从而加深对「局部最优」和「全局最优」的理解。
先枚举，再贪心
枚举题目的其中一个变量，将其视作已知条件，然后在此基础上贪心。
也可以枚举答案，检查是否可以满足要求。（类似二分答案）
区间贪心
区间贪心有如下经典问题：
- 不相交区间（单机器调度/活动安排）：给定一些区间，从中选出尽量多的两两互不相交的区间。
- 区间分组（任务调度/会议室）：给定一些区间，把这些区间分成最少的组，使得每组内的区间互不相交。
- 区间选点（射气球，Interval Stabbing）：给定一些区间，在数轴上放置最少的点，使得每个区间都包含至少一个点。最少要放置多少个点？
- 区间覆盖（灌溉花园）：给定一些区间，从中选出尽量少的区间，覆盖一条指定线段 [s,t]。
一般来说，区间合并问题（2.5 节）是按左端点排序，其余大多数区间贪心是按右端点排序。请读者在做题后，仔细体会为什么要这样排序。
不相交区间
字符串贪心
字典序最小/最大 字典序的定义如下：
对于两个字符串 a 和 b，从左到右依次比较字符 a[i] 和 b[i] 的 ASCII 值的大小。 a[i]=b[i] 时，如果 a[i]<b[i]，那么 a 的字典序更小，否则 b 的字典序更小。 如果没有出现 a[i]=b[i]，则短的字符串字典序更小。 如果两个字符串的长度和内容均相同，那么两个字符串的字典序一样。 字典序的定义也可以推广到数组上，按照上述方法比较两个数组的字典序。
参考
分享丨【算法题单】贪心算法（基本贪心策略/反悔/区间/字典序/数学/思维/构造） - 讨论 - 力扣（LeetCode）
作者：灵茶山艾府 链接：https://leetcode.cn/discuss/post/g6KTKL/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。