贪心模型汇总
贪心算法模型整理
贪心模型不重要，重要的是思维
1. 区间调度问题
例题：最多可以参加多少个活动？有一系列活动，每个活动有开始时间和结束时间，问一个人最多能参加多少个不重叠的活动。
贪心策略：按结束时间从小到大排序，每次选择结束最早且不与已选区间重叠的区间。
2. 区间覆盖问题
例题：最少的箭引爆气球。在平面上有一些气球，每个气球有水平方向的直径范围，垂直射出的箭可以在x位置引爆所有x∈[start,end]的气球，求引爆所有气球的最少箭数。
贪心策略：按结束坐标排序，每次在第一个未覆盖区间的结束位置放箭，移除所有包含该点的区间。
3. 分配问题
例题：饼干分配。有孩子数组g[i]表示每个孩子的胃口值，饼干数组s[j]表示每块饼干的大小。每个孩子最多分一块饼干，求最多能满足多少个孩子。
贪心策略：将孩子胃口和饼干大小都排序，用最小的饼干满足最小的胃口。
4. 跳跃游戏问题
例题：跳跃游戏II。给定非负整数数组，每个元素代表在该位置可以跳跃的最大长度，求从第一个位置跳到最后一个位置的最少跳跃次数。
贪心策略：维护当前能到达的最远位置和边界，到达边界时跳跃次数加一。
5. 买卖股票问题
例题：买卖股票的最佳时机II。给定股票每天的价格，可以进行多次交易（买之前必须卖出之前的），求最大利润。
贪心策略：将所有正利润累加，今天价格比昨天高就交易。
6. 分糖果问题
例题：分发糖果。n个孩子站成一排，每个孩子有一个评分。要求：每个孩子至少1个糖果；评分更高的孩子必须比相邻的孩子糖果多。求最少需要多少糖果。
贪心策略：先从左到右遍历，右边比左边高分就多给糖；再从右到左遍历，左边比右边高分且糖果不多就更新。
7. 加油站问题
例题：加油站。在环形路上有N个加油站，每个加油站有汽油gas[i]，到下一站耗油cost[i]。从某个加油站出发，求能否绕环路一周，如果能返回起点编号。
贪心策略：计算总油量，如果总油量足够则一定有解；遍历寻找油量累积不会为负的位置作为起点。
8. 任务调度问题
例题：任务调度器。给定CPU需要执行的任务列表，相同任务间有冷却时间n。求完成所有任务所需的最少时间。
贪心策略：优先安排出现次数最多的任务，按照冷却时间合理安排其他任务。
9. 哈夫曼编码问题
例题：文件合并。有多个文件需要合并，每次只能合并两个文件，合并代价为两个文件大小之和。求将所有文件合并成一个文件的最小总代价。
贪心策略：每次选择最小的两个文件合并，将合并后的文件放回，重复直到只剩一个文件。
10. 删数问题
例题：移掉K位数字。给定一个以字符串表示的非负整数num和一个整数k，移除k位数字，使得剩下的数字最小。
贪心策略：维护单调递增栈，遇到更小的数字就弹出栈顶元素（相当于删除数字）。
11. 划分字母区间
例题：划分字母区间。字符串S由小写字母组成，要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
贪心策略：记录每个字母最后出现的位置，遍历时更新当前片段的结束位置，到达结束位置就划分片段。
12. 根据身高重建队列
例题：根据身高重建队列。假设有打乱顺序的一群人，每个人用(h,k)表示，h是身高，k是前面身高大于等于h的人数。请重建这个队列。
贪心策略：先按身高降序、k值升序排序，然后按k值作为索引插入到结果队列中。
13. 无重叠区间
例题：无重叠区间。给定一个区间集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
贪心策略：按结束时间排序，计算最多能保留的不重叠区间数，总数减去这个数就是需要移除的数量。
14. 用最少数量的箭引爆气球
例题：用最少数量的箭引爆气球。在二维空间中有许多球形的气球，在x轴方向有一个直径。一支箭可以在坐标x处垂直射出，引爆所有满足start ≤ x ≤ end的气球。求引爆所有气球所需的最小弓箭数。
贪心策略：按结束坐标排序，每次在第一个未引爆气球的结束位置射箭，引爆所有包含该点的气球。
15. 单调递增的数字
例题：单调递增的数字。给定一个非负整数N，找出小于或等于N的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
贪心策略：从右向左遍历，遇到逆序就对前一位减1，后面所有位都变成9。
16. 优势洗牌
例题：优势洗牌。给定两个大小相等的数组A和B，A相对于B的优势可以用满足A[i] > B[i]的索引i的数目来描述。返回A的任意排列，使其相对于B的优势最大化。
贪心策略：将A和B排序，用A中最小的能大于B[i]的数对应当前B[i]，否则用A中最小的数消耗B中最大的数。
17. 最低加油次数
例题：最低加油次数。汽车从起点出发驶向目的地，沿途有加油站，每个加油站有位置和油量。求到达目的地所需的最少加油次数。
贪心策略：用最大堆存储经过的加油站油量，没油时从堆中取最大的油量加油。
18. K次取反后最大化的数组和
例题：K次取反后最大化的数组和。给定一个整数数组A和整数K，最多可以取反K次（每次可以选一个数变为相反数），返回可能的最大数组和。
贪心策略：按绝对值从大到小排序，优先取反负数；如果K还有剩余且为奇数，取反最小的数。
19. 重构字符串
例题：重构字符串。给定一个字符串，重新排列这个字符串，使得相邻的字符不相同。
贪心策略：统计字符频率，每次选择剩余次数最多且不与前一个字符相同的字符。
20. 划分数组为连续子序列
例题：划分数组为连续子序列。给定一个整数数组，判断是否能将数组划分为若干个连续递增的子序列，每个子序列长度至少为3。
贪心策略：统计每个数字的出现次数，对于每个数字，优先接在已有的序列后面，否则尝试开启新的连续序列。