大家好，今天是我们贪心算法章节的第三阶段，前面我们讲过的几道题不知道大家理解的情况如何，还是那句话，贪心算法没有固定的套路与模板，一道题一个思路，我们要多思考这样慢慢地我就就可以水到渠成。今天我们接着昨天的内容继续我们的贪心算法章节。
第一题对应力扣编号为134的题目加油站
我们来到我们今天的第一道题，这道题目叫做加油站，其实这道题目我感觉对于刚刚接触贪心算法不久的我还是很有难度的，难在不知道贪心贪在哪里，但是其实我们仍可以静下来好好思考一下题意，我们先来一起看一下这道题目：
题目的大致意思相信读完题目就可以了解，就是我们开往一个新的加油站我们的车会消耗一部分油同时又会补充一部分新的油，题目问我们我们从哪一个加油站出发可以循环一圈，首先我们来看一下题目给出的示例，我们如果从0号加油站出发，上来补充1个汽油消耗3个汽油，直接没法跑了，如果我们从1号汽油站出发，上来补充2个汽油但是消耗4个汽油还是不行，直到我们发现如果我们从3号汽油站出发我们是可以的，那么我们总体来看的话为什么我们3号加油站前面的不行呢？是不是因为我获得的汽油太少而消耗的汽油太多，因此判断能不能走完全程的关键就在于我们的补充量与消耗量的差值尽可能为正，如果一旦为负的话不仅仅这个加油站不可以，前面的所有的都不可以，可能有的朋友就会有疑问为什么呢？其实大家一想便知道我这个加油站会永远阻碍我的剩余油量为正，如果想走完全程是必须要经过这个加油站的，那我们就可以设置一个变量来存储剩余油量，如果发现为负数了我们就从它的下一个加油站开始，同时我们要重新统计剩余油量，还有如果我全程的剩余油量为负数就一定走不完，因为消耗的多补充的少自然走不完全程，根据这个思路我们可以写出代码：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int CurSum = 0; //存储当前的油量
int totalSum = 0; //表示跑一圈消耗油量的情况
int start = 0; //记录符合条件的起始位置
for (int i = 0; i < gas.size(); ++i)
{
CurSum += (gas[i] - cost[i]);
totalSum += (gas[i] - cost[i]);
if (CurSum < 0)
{
start = i + 1;
CurSum = 0;
}
}
if (totalSum < 0) return -1;
return start;
}
};是这样的思路，我还是要补充说明一下为什么一旦发现为负数那么前面的都不可以作为起点，原因可以借助一张图来理解：
| 起点 | CurSum < 0 |
大家来看我这个表格，如果我以当前作为起点的话，如果我能累加到CurSum小于0的位置，说明起点到这个位置的剩余油量累加和必须为正，那么既然全程为负数就说明前面的从开头到起点必然是负数那么这个起点是不能作为我们题目的起点的，这样解释一下大家或许可以明白。
第二题对应力扣编号为860的题目柠檬水找零
我们临时更换一下题目顺序，这一道题目应该是稍微简单一点点我们可以放到前面来讲，我们一起来看一下这一道题目：
题目是看看我们最后是不是可以正确找零，其实大家先清楚一点就是我最后只剩一张10美元的钞票那么我们如果有一个需要找5美元的顾客那么我们是没有办法找零的，那我们一起来看看这道题目的解题思路，其实题目为什么比较简单就是我们需要考虑的情况比较少，就是三种钞票，5美元，10美元，20美元，如果是5美元的话就直接收下，如果是10美元的话就消耗5美元然后增加10美元，如果是20美元的话我们是先考虑给出一张10美元的和一张5美元的，如果不具备我们最后考虑3张5美元的，为什么要先考虑10美元的呢？其实不能难想，因为我们的5美元的比较万能，因为它既可以找零20美元的也可以找零10美元的，这是一个思考点，因此我们会先考虑用10美元的找零，根据这个思路我们看一下代码应该如何写：
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0, twenty = 0; //记录三种钞票的数量
for (int bill : bills)
{
//情况1
if (bill == 5) five++;
//情况2
if (bill == 10)
{
if (five <= 0) return false;
five--;
ten++;
}
//情况3
if (bill == 20)
{
//如果5美元的与10美元的钞票都还够用
if (five > 0 && ten > 0)
{
five--;
ten--;
twenty++;
}
else if (five >= 3)
{
five -= 3;
twenty++;
}
else return false;
}
}
return true;
}
};第三题对应力扣编号为135的题目分发糖果
我们来到今天的第三题，这道题估计比上面的柠檬水找零要难一些，所以我放到下面来讲，我们先一起看一下题目要求：
根据力扣上面的难度显示这个已经可以算是困难了，读完题目我大体明白了题目的意思就是就算评分是0的孩子我也要至少给他一个糖果，相邻两个孩子评分更高的将会获得更多的糖果，其实大家看这个示例一估计也不难懂，我首先看评分为0的孩子给他一个糖果，那么相邻的两个孩子评分都比他高都是多给一块糖果，但是第一个与第三个孩子不相邻所以不需要比较，比较对象仅仅局限于相邻的孩子，我们一起来看一下这道题目我们应噶如何考虑，首先我们不要直接遍历这样很容易顾此失彼，很容易出问题，不是右边比左边大就是左边比右边大，我们正确的思路应该是先确定一边再去确定另一边，因此我们可以分成两种情况去考虑，第一种我们只看右边孩子评分比左边孩子大的情况，第二种情况我们只看左边孩子比右边孩子评分大的情况，但是大家要注意两种情况的遍历顺序是相反的，第一种应该是从前往后遍历，因为我们主要更新的是右边孩子的糖果数量，而第二种是从后往前遍历因为我们主要更新的是左边孩子的糖果数量，最后大家注意我们既然要同时符合两种情况，所以我们每一个小朋友应该获得的糖果数应该是两种情况的最大值，
大家看这幅图这是一个示例，很明显从左往右遍历这种情况是有问题的，比如说我们相邻的孩子我们要求评分高的获得的糖果也应该多，但是大家看到rating数组3，4，5的情况很明显不对，4没有5高但是4的糖果却多这是不合理的，因此我们就还要考虑第二种情况两种情况去最大值才正确，我给出大家本道题目的解题代码：
class Solution {
public:
int candy(vector<int>& ratings) {
//大家注意我们初始值应该设置为1因为就算评分为0也应该给一块糖果
vector<int> candyVec(ratings.size(), 1);
//从前往后遍历
for (int i = 1; i < ratings.size(); ++i)
{
if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}
//从后往前遍历
for (int i = ratings.size() - 2; i >= 0; --i)
{
if (ratings[i] > ratings[i + 1]) candyVec[i] = max(candyVec[i + 1] + 1, candyVec[i]);
}
int result = 0;
for (int i = 0; i < ratings.size(); ++i) result += candyVec[i];
return result;
}
};其实解题代码难度不大，主要还是思路，大家一定要多思考。我们接着进入下一道题目。
第四题对应力扣编号为406的题目根据身高重建队列
这道题目听说挺难的，当然我还是第一次看，估计不会轻松，那就一起看一下题目：
题目看似好复杂，尤其是下面的解释也是很长，看完题目我大致明白了，题目还是比较抽象的，就是我每一个people[i]都表示我当前这个人的身高和前面整好有几个身高大于等于他的人，这样示例一的解释大家就可以看明白了，看的是身高以及比其高的人数，比如说原数组编号0的人身高是7，后面的0表示没有身高更高获=或者相同的人排在他前面，编号为1的人类似，编号最后的人身高为5但前面有2个身高大于等于它的人，这样刚好就是前面这两个人，后面的都类似，这样就可以重新排列出新的队列，我们一起来思考一下应该如何解决这道题目，其实怎么说呢？这道题目我们其实我们应该是按照身高从大到小排序，这样的话其实根据k我插入元素是不会影响身高关系的，比如我们的示例一[7,0],[7,1]可能中间会插入[6,1]有朋友可能会疑惑你这样身高的顺序乱了呀，我说对的但是我的6本来就比7小，我插入中间会影响我7前面有一个身高大于等于7的吗？不会的，这就是排序的功能，我们按照身高排完序后那么我们就主要考虑k就可以，按照k的大小去选择插入位置，这就是我们的思路，这是插入过程大家可以看一下：
我们来看一下这道题目的解题代码如何写：
class Solution {
public:
//自定义排序方法，我们先按照身高排序如果身高一样k小的在前面
static bool cmp(const vector<int> &a, const vector<int> &b)
{
if (a[0] == b[0]) return a[1] < b[1];
else return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
vector<vector<int>> que;
for (int i = 0; i < people.size(); ++i)
{
//取出k进行插入
int partition = people[i][1];
que.insert(que.begin() + partition, people[i]);
}
return que;
}
};今日总结
其实今天的题目难度不小，我们了解到了多维度的问题我们一定要分开处理，不要一并处理，还有贪心算法其实只要搞清楚思路之后代码量都不会太大，大家还是多锻炼，我们今天的这几道题目质量还是很高的，大家多思考一下，那么我们下次再见！