目录
（3）122. 买卖股票的最佳时机 II - 力扣（LeetCode）
一、理论基础
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。
> 什么时候用贪心？
hhh卡哥说没有具体场景，，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。贪心有时候就是常识性的推导，所以会认为本应该就这么做！
> 一般解题步骤？
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
确实过于理论化。。。。~一般都会涉及到排序 、找规律、反证其可行性
我们直接练题！！！
二、题目练习
（1）455. 分发饼干
局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。
最终代码：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
//给孩子和饼干排序
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int res=0;
int index=s.size()-1;
//将大饼干优先分给胃口大的孩子
for(int i=g.size()-1;i>=0;i--)//遍历胃口
{
if(index>=0&&s[index]>=g[i]) //遍历饼干
{
index--; //可以分配就指向下一个更大的饼干
res++;
}
}
return res;
}
};感觉还挺简单的，难在找到他的局部最优性质
（2）53. 最大子数组和 - 力扣
解法一： 可以暴力，但是时间复杂度会高
解法二：dp,之前我们有做过~
解法三：贪心
如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res=INT_MIN; //一个很小的负数
int cnt=0;
for(int i=0;i<nums.size();i++){
cnt+=nums[i];
if(cnt>res)res=cnt;
if(cnt<=0) cnt=0; //加上之后非正了，cnt=0相当于重置最大子序起始位置
}
return res;
}
};（3）122. 买卖股票的最佳时机 II - 力扣（LeetCode）
在dp中我们也做过这道题~~，找到局部最优性质后，用贪心更简单一点
局部最优：收集每天的正利润，全局最优：求得最大利润。
是不是特别简单哈哈哈
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};（4）860. 柠檬水找零 - 力扣（LeetCode）
只需要维护三种金额的数量，5，10和20。
- 情况一：账单是5，直接收下。
- 情况二：账单是10，消耗一个5，增加一个10
- 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
账单是20的情况，为什么要优先消耗一个10和一个5呢？
因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！
所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0, twenty = 0;
for (int bill : bills) {
// 情况一
if (bill == 5) five++;
// 情况二
if (bill == 10) {
if (five <= 0) return false; //找不了
ten++;
five--;
}
// 情况三
if (bill == 20) {
// 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着
if (five > 0 && ten > 0) {
five--;
ten--;
twenty++; // 其实这行代码可以删了，因为记录20已经没有意义了，不会用20来找零
} else if (five >= 3) {
five -= 3;
twenty++; // 同理，这行代码也可以删了
} else return false;
}
}
return true;
}
};
（5）905. 区间选点 - AcWing题库
数轴上有一些区间，在数轴上选取几个点，要求每个区间上最少有一个点。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r; //左右结点
bool operator< (const Range &W)const
{
return r < W.r; //按照右端点从小到大排序
}
}range[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) cin>>range[i].l>>range[i].r;
sort(range, range + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
if (ed < range[i].l) //新的左端点不能覆盖右端点
{
res ++ ; //需要新增一个结点
ed = range[i].r; //更新右端点
}
cout<<res;
return 0;
}
（6）AcWing 908. 最大不相交区间数量
与上一道区间选点的题一样，一定要是对右端点从小到大排序！！！！
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r; //左右结点
bool operator< (const Range &W)const
{
return r < W.r; //按照右端点从小到大排序
}
}range[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) cin>>range[i].l>>range[i].r;
sort(range, range + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
if (ed < range[i].l) //新的左端点不能覆盖右端点
{
res ++ ; //需要新增一个结点
ed = range[i].r; //更新右端点
}
cout<<res;
return 0;
}
（7）906. 区间分组 - AcWing题库
等效于把尽可能多的区间塞进同一组，要满足range[i].l > heap.top
- 把所有区间按照左端点从小到大排序
- 从前往后枚举每个区间，判断此区间能否将其放到现有的组中
- heap有多少区间，就有多少组
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l; //按照左端点排序！！！！
}
}range[N];
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ )
{
int l, r;
cin>>l>>r;
range[i] = {l, r};
}
sort(range, range + n);
//小根堆（每次弹出最小的数）--每个组的右端点存储在 heap 中
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < n; i ++ )
{
//新区间的左端点大于等于堆顶的右端点
if (heap.empty() || heap.top() >= range[i].l){
heap.push(range[i].r); //开一个新组，记录其右端点
}
else { //可以合并
heap.pop();//取出右端点最小的区间
heap.push(range[i].r);//保留这个右端点较大的区间
}
}
cout<<heap.size();
return 0;
}
（8）907. 区间覆盖 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e9+10;
#define PII pair<int ,int>
PII a[N];
int s,t,n;
int main()
{
cin>>s>>t;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i].first>>a[i].second;
}
sort(a,a+n);
int res=0;
bool flag=false;//默认无法完全覆盖
for(int i=0;i<n;i++)
{
int j=i,r=-M;
while(j<n&&a[j].first<=s)
{
r=max(r,a[j].second);
j++;
}
if(r<s)
{
res=-1;
break;
}
res++;
//最后更新的右端点大于给定区间---能覆盖
if(r>=t)
{
flag=true;
break;
}
s=r;//每次更新左端点为能覆盖给定区间的最大的右端点
i=j-1;
}
if(!flag) res=-1;
cout<<res;
return 0;
}（9）148. 合并果子 - AcWing题库
在学优先队列的时候做过这道题~~
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
ll ans;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
priority_queue<ll,vector<ll>,greater<ll>> pq;
while(n--)
{
ll x;
cin>>x;
pq.push(x);
}
while(pq.size()>=2)
{
ll x=pq.top();pq.pop();
ll y=pq.top();pq.pop();
ans+=x+y;
pq.push(x+y);
}
cout<<ans;
return 0;
}
（10）913. 排队打水 - AcWing题库
需要将打水时间最短的人先打水 --计算前缀和数组的和（不包含最后一个人）
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
int main()
{
int n;
cin>>n;
vector<LL> a(n+1);
vector<LL> qz(n+1,0);//前缀和数组
for(int i=1;i<=n;i++) cin>>a[i];
//从小到大排序
sort(a.begin(),a.end());
//计算排序后的前缀和数组（不用计算最后一个）
for(int i=1;i<n;i++) qz[i]=qz[i-1]+a[i];
//求前缀和的sum
cout<<accumulate(qz.begin()+1,qz.end(),0ll);
return 0;
}（11）104. 货仓选址 - AcWing题库
贪心策略：一开始自己也猜到了哈哈哈就是中位数
排序 +中位数
#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{
cin>>n;
for (i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);//排序
int sm=a[n/2+1];//中位数
for (i=1;i<=n;i++)
ans=ans+abs(a[i]-sm);//统计和中位数之间的差
cout<<ans;
return 0;
}