贪心的本质是选择每⼀阶段的局部最优，从而达到全局最优。
- 贪心算法⼀般分为如下四步：
- 将问题分解为若干个问题
- 找出适合的贪心策略
- 求解每⼀个子问题的最优解
- 将局部最优解堆叠成全局最优解
分配问题
455发饼干
135分发糖果
区间问题
452. 用最少数量的箭引爆气球
链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
问题可以简化为贪心去除最多相互重合区间，最多去除几次能将所有区间去除
所以关键就是怎么快速找到重合的区间，可以对区间的上界或者下届进行排序
我选择的是对下界排序，标记第一个区间的上界，并计数，循环判断下一个区间的下届是否小于标记的上界，小于等于则说明重合。当不重合时，将标记上界更新为当前区间的上界，计数加一，作为新的重合区间判断标准
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) {
return 0;
}
sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {
return u[1] < v[1];
});
int pos = points[0][1];
int ans = 1;
for (const vector<int>& balloon: points) {
if (balloon[0] > pos) {
pos = balloon[1];
++ans;
}
}
return ans;
}
};
435. 无重叠区间
链接：https://leetcode-cn.com/problems/non-overlapping-intervals/
题目等价于 选出最多数量的区间，使得它们互不重叠，如何获得最多数量，即两个重合的区间删除其中一个后留下的区间的上界要尽可能小，因此对区间上界排序，题目也变成找不重合区间
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int n=intervals.size();
sort(intervals.begin(),intervals.end(),[](vector<int>&a,vector<int>&b){return a[1]<b[1];});
int end=intervals[0][1];
int ans=1;
for(int i=1;i<n;++i){
if(intervals[i][0]>=end){
ans++;
end=intervals[i][1];
}
}
return n-ans;
}
};
序列问题
两维度权衡问题
股票贪心
其他问题
605. 种花问题
链接：https://leetcode-cn.com/problems/can-place-flowers/
贪心把从头开始能种的位置全种上 种花需要考验前面位置和后面位置 通过遍历筛选前面位置可行的
很简单，从第一个位置开始遍历，为0情况就判断下一个位置不为1就种花并跳过两格，为1情况就直接跳两格。因为逢1就跳两格，所以当当前位置为0时前面方向的花位置一定没有问题，只需判断后置位是否存在问题
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int f=flowerbed.size();
if(n==0)return true;
for(int i=0;i<f;++i){
if(flowerbed[i]==1)++i;
else if(i+1<f&&flowerbed[i+1]==0){
flowerbed[i]=1;
++i;
n--;
if(n==0)return true;
}else if(i==f-1){
n--;
}
}
return n==0;
}
};