贪心算法是一种常见的算法思想，其特点就是通过每次都选择局部最优来达到实现全局最优的目的。例如让你从一堆钞票中拿走10张，你为了达到拿到最大金额的目的，必定会每次都拿走最大面额的钞票，这就是贪心算法的思想。在刷题过程中，贪心算法的题目一般没有固定的套路，所以其最大的难点就是如何实现局部最优。
而实现局部最优的方法也因题而异，有时候就是常识性的推导。我们唯一可以做的，就是手动模拟一下，感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。
一、简单题目
| LeetCode题目 | 相关题目类型 | 题目类型分析 | 题目思路 | 相关链接 |
|---|---|---|---|---|
| 455 | 分发饼干（简单难度） | 一对一，将不同尺寸的饼干分给不同胃口的孩子，尽可能满足最多孩子的胃口 | 小尺寸饼干分给小胃口孩子 | https://leetcode-cn.com/problems/combinations/ |
| 1005 | K次取反后最大化的数组和（简单难度） | 将数组中的数进行k次取相反数后数组和最大，可以对同一个数反复取相反数。 | 数组中的负数取反，负数的绝对值越大优先级越高；然后反复取同一个最小的非负数（实现上需要将数组按绝对值大小排序） | https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/ |
| 860 | 柠檬水找零（简单难度） | 付钱找零，判断是否可以全部正确找零 | 多种找零情况下优先找面额大的钞票 | https://leetcode-cn.com/problems/lemonade-change/ |
455. 分发饼干（简单难度）
/*该题目的目标是满足尽可能多的孩子的胃口，
那么对于每个孩子就是尽可能用最小尺寸的饼干来其胃口，
即尽可能做到大饼干喂给大胃口孩子，小饼干喂给小胃口孩子。
*/
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());//孩子按胃口大小从小到大排序
sort(s.begin(),s.end());//饼干按尺寸大小从小到大排序
int index = 0;
// 遍历每块小饼干
for(int i = 0;i < s.size();++i){
// 如果孩子index的胃口可以被s[i]满足，则index++
if(index < g.size() && g[index] <= s[i]){
index++;
}
}
return index;
}
1005. K 次取反后最大化的数组和（简单难度）
/*
该题目是将数组中的某些数进行k次取相反数后数组和最大，可以对同一个数反复取相反数。
根据题意可知，使最后数组和最大的策略是：
1、首先将数组中的负数取反，负数的绝对值越大优先级越高；
2、如果此时数组中负数全取反后，k依旧不为0：
如果k是偶数，则不用管，对同一个数进行偶数次取反还是原数
如果k是奇数，则将此时数组中最小的数取反即可。
在实现上：首先需要将数组按绝对值从大到小排列，然后遍历数组,将负数进行取反同时k--；
然后判断剩下的k是否是奇数，如果是奇数，将数组最后一个值取反即可
*/
static bool cmp(int a, int b) {
return abs(a) > abs(b); //大于表示从大到小
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
// 将数组按照绝对值进行从小到大的排序
sort(nums.begin(), nums.end(), cmp);
// 遍历数组，将负数变为整数，同时K--
for (int i = 0; i <nums.size(); i++) {
if (nums[i] < 0 && k > 0) {
nums[i] *= -1;
k--;
}
}
// 如果此时k依旧为奇数，则将最小的非负数反复转换为其相反数即可
if (k % 2 == 1) nums[nums.size() - 1] *= -1;
int res = 0;
// 求最大数组和
for (int a : nums) res += a;
return res;
}
本题的难点可能就是如何将数组按照想要的按绝对值大小进行排序。
860. 柠檬水找零（简单难度）
/*在找零的过程中,显然应该优先找面额大的，这样后续的找零才能尽可能满足
有如下三种情况：
-情况一：账单是5，直接收下。
-情况二：账单是10，消耗一个5，增加一个10
-情况三：账单是20，优先消耗一个10和一个5，如果不够,再消耗三个5*/
bool lemonadeChange(vector<int>& bills) {
// 统计5和10的数量,不用统计20,因为20无法找零
int five_count = 0;// 手中5美元的数量
int ten_count = 0;// 手中10美元的数量
// 遍历账单
for(int bill:bills){
// 如果当前顾客付了5美元
if(bill==5) five_count++;
// 如果当前顾客付了10美元
else if(bill==10){
ten_count++;
// 如果有1张以上的5元零钱
if(five_count>0) five_count--;
else return false;
}
// 如果当前顾客付了20美元
else if(bill==20){
// 如果同时有5元和10元的零钱
if(ten_count>0&&five_count>0){
ten_count--;
five_count--;
}
// 如果只有3张以上的5元零钱
else if(five_count>=3) five_count-=3;
else return false;
}
}
return true;
}
二、序列题目
53. 最大子数组和（简单难度）
时间复杂度：O(n) 空间复杂度：O(1)
/*贪心算法：全局最优：选取最大“连续和”，
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，
因为负数加上下一个元素 “连续和”只会越来越小。
实现：遍历数组nums,计算当前累计和，如果累计和为负数立刻重置为0
*/
int maxSubArray(vector<int>& nums) {
int maxSum = INT32_MIN;//要尽可能快的更新
int curSum = 0;//当前子序和
// 遍历数组
for (int i = 0; i < nums.size(); i++) {
curSum += nums[i];
// 记录最大子序和
maxSum=max(maxSum,curSum);
// 如果当前子序和小于等于零，立刻放弃该子序和
if (curSum <= 0) curSum = 0;
}
return maxSum;
}
376. 摆动序列（中等难度）
/*贪心算法,该题目标是从一个数组中找出满足摆动序列的最长子数组的长度
这里的摆动序列可以不连续，首先要解决的就是如何判断一个数组是否是摆动序列？
判断相邻的两个差值是否异号
思路： 首先定义1个结果数组作为最长序列，将数组的第1个元素加进去（确保数组元素大于1）
遍历原始序列中的每个元素：计算出当前差值nums[i]-nums[i-1]
判断是否和上一个差值lastCha异号,如果满足则加入结果数组并且更新lastCha，否则跳过去*/
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()==1) return 1;
// 结果序列
int curCha = 0;//当前差值
int lastCha = 0;//前一个差值
vector<int> res;
res.push_back(nums[0]);//默认第一个数在结果序列中
// 遍历整个序列
for(int i=1;i<nums.size();i++){
curCha = nums[i]-nums[i-1];//计算当前序列
// 如果上一个差值小于等于0并且当前差值大于0
if(curCha>0&&lastCha<=0){
res.push_back(nums[i]);
lastCha = curCha;
}
// 上一个差值大于等于0并且如果当前差值小于0
if(curCha<0&&lastCha>=0){
res.push_back(nums[i]);
lastCha = curCha;
}
}
return res.size();
}
738. 单调递增的数字（中等难度）
整数转换为字符串：to_string(n)
字符串转换为整数：stoi(strNum)
数字字符可以直接进行比较：’8’<’9’
/*贪心算法,显然n是单调递增时，直接返回n
如果n不是单调递增，比如strNum[i-1]>strNum[i]
那么我们只需要将strNum[i-1的数字-1,将i之后的数字设为9
例如10修改为9;332修改为229*/
int monotoneIncreasingDigits(int n) {
string strNum = to_string(n);//将数字转换为字符串
// flag用来标记赋值9从哪里开始
int flag = strNum.size(); // 记录第一个开始减少的索引位置
// 从右向左扫描数字，减小的第一个数设置为flag
for (int i = strNum.size() - 1; i > 0; i--) {
// 如果左边的数大于右边的数，说明此时没有单调递增
if (strNum[i-1] > strNum[i] ) {
flag = i;
strNum[i-1]--;
}
}
// 如果n不是单调递增，则执行flag及其之后的数字都改为9
for (int i = flag; i < strNum.size(); i++) strNum[i] = '9';
return stoi(strNum);// 字符串数字转换为整数
}
三、股票问题
| LeetCode题目 | 相关题目类型 | 题目类型分析 | 题目思路 | 相关链接 |
|---|---|---|---|---|
| 122 | 买卖股票的最佳时机II（中等难度） | 一个股票在多天的价格走势数组，可以多次买入卖出，求获得的最大利润 | 价格数组中的相邻元素的差值，将差值为正的数都加起来 | https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/ |
| 714 | 买卖股票的最佳时机含手续费（中等难度） | 最低值买，最高值（如果算上手续费还盈利）就卖 | https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/ |
122. 买卖股票的最佳时机 II（中等难度）
class Solution {
public:
/*贪心算法：该题是可以多次买卖，且每次没有成本
那么只要相邻两位是递增，则可以将其差值累计到利润中*/
int max_profit=0;
for(int i=1;i<prices.size();i++){
int cur=prices[i]-prices[i-1];
if(cur>0) max_profit+=cur;//相邻差值为正数
}
return max_profit;
};
714. 买卖股票的最佳时机含手续费（中等难度）
本题有了手续费，就要关系什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以手续费的情况。
如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。
此时无非就是要找到两个点，买入日期，和卖出日期。
- 买入日期：其实很好想，遇到更低点就记录一下。
- 卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。
所以我们在做收获利润操作的时候其实有三种情况：
- 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
- 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
- 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
贪心算法C++代码如下：
答案如下：
/*贪心算法：该题是可以多次买卖，但是每次都需要支付手续费fee
贪心策略:最低值买，最高值（如果算上手续费还盈利）就卖
那么只要相邻两位是递增，则可以将其差值累计到利润中*/
int maxProfit(vector<int>& prices, int fee) {
int max_profit=0;
int min_price=prices[0];// 买入价格
// 遍历价格数组，找到相邻差值为正数，加到利润里
for(int i=1;i<prices.size();i++){
// 情况二：如果当天价格比之前的最低价格低，则记录买入价格
if(min_price>prices[i]) min_price=prices[i];
// 情况三：如果当天价格比之前的最低价格高，但是利润小于手续费
else if(min_price<=prices[i]&& prices[i]<=min_price+fee)continue;
// 如果当天价格比之前的最低价格高，而且利润大于手续费
else if(prices[i] > min_price + fee){
max_profit+=prices[i]-min_price-fee;//假设今天卖出，则利润等于当前价格-买入价格-手续费
//情况一,假设明天还在涨,则明天求利润需要-今天收入（当前价格）+手续费
min_price = prices[i]-fee;
}
}
return max_profit;
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
从代码中可以看出对情况一的操作，因为如果还在收获利润的区间里，表示并不是真正的卖出，而计算利润每次都要减去手续费，所以要让minPrice = prices[i] - fee;，这样在明天收获利润的时候，才不会多减一次手续费！
大家也可以发现，情况三，那块代码是可以删掉的，我是为了让代码表达清晰，所以没有精简。
四、区间题目
| LeetCode题目 | 相关题目类型 | 题目类型分析 | 题目思路 | 相关链接 |
|---|---|---|---|---|
| 55 | 跳跃游戏（中等难度） | 跳跃覆盖范围可以不可以覆盖到终点的问题 | 每次移动取最大跳跃步数来得到最大的覆盖范围，每移动一个单位，就更新最大覆盖范围，一旦超过终点即可返回true。 | https://leetcode-cn.com/problems/jump-game/ |
| 45 | 跳跃游戏II（中等难度） | 当前覆盖范围和下一虚拟步的覆盖范围 | 在当前步覆盖范围不断前进，不断更新当前虚拟步的最大距离，当前覆盖范围走完且不是终点后，最小步数+1，更新当前步数的范围，如果此时当前步范围覆盖了数组终点则直接返回结果 | https://leetcode-cn.com/problems/jump-game-ii/ |
| 134 | 加油站（中等难度） | 起始站点存在则一定只有一个 | 如果curSum<0则[0,j]之间一定没有起始站点，排除思想 | https://leetcode-cn.com/problems/gas-station/ |
| 452 | 用最少数量的箭引爆气球（中等难度） | 二维数组排序，判断其中的区间边界是否重叠 | 先将气球按照起始位置或者终止排序；然后比较当前气球和前一个气球是否重合，不重合增加一只箭，重合则更新当前气球的右边界（取当前气球右边界和前一个气球右边界的最小值） | https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/ |
| 435 | 无重叠区间（中等难度） | 二维数组排序，判断其中的区间边界是否重叠 | 先将二维数组按照第二维数组的起点从小到大排序，然后比较当前区间的左边界和前一个区间的右边界来判断是否重叠，没有重叠跳过去，重叠了则结果+1，并且将当前区间的右边界取最小值（相当于默认删除右边界区间较大的那个重叠区间） | https://leetcode-cn.com/problems/non-overlapping-intervals/ |
| 763 | 划分字母区间（中等难度） | 分割字符串，将同一个字母都圈在一个区间里 | 其等价于找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。所以我们可以遍历两次字符串， 第1次遍历统计每个字符出现的最后位置； 第2次遍历寻找分割点（字符最远下标与当前下标相等）. | https://leetcode-cn.com/problems/partition-labels/ |
| 56 | 合并区间（中等难度） | 合并区间，可能连续n个区间可以合并在一起 | 需要一个二重循环，外层负责遍历两个相邻区间，内层负责判断是否是否重叠，重叠了则合并边界将其加入结果 | https://leetcode-cn.com/problems/merge-intervals/ |
55. 跳跃游戏（中等难度）
利用能量格子思路的答案如下：
/*贪心算法：从索引0出发，走到索引n-1。每个索引i最多走nums[i]步
想象你是那个在格子上行走的小人，格子里面的数字代表“能量”，你每走一个格子需要消耗一个“能量”。
每次走到一个格子的时候，你检查现在格子里面的“能量”和你自己拥有的“能量”哪个更大，取更大的“能量”！
如果你有更多的能量，你就可以走得更远*/
bool canJump(vector<int>& nums) {
if(nums.size()==1) return true;// 只有一个元素，默认能达到
int i=0;//起步位置
int cur = nums[0];//手中拥有的能量
// 如果当前能量不为空则可以前进
while(cur!=0){
cur--;//能量-1
cur=max(cur,nums[i]);// 如果i上的能量更多，丢掉手上的cur
i++;//位置+1
if(i>=nums.size())return true;
}
return false;
}
45. 跳跃游戏 II（中等难度）
本题最后要计算最小步数，那么就要想清楚什么时候步数+1？
该代码需要统计两个覆盖范围：当前这一步的最大覆盖（确实采取了）curCover和下一虚拟步的最大覆盖（假设采取）nextCover。
具体代码如下：
int jump(vector<int>& nums) {
// 只有一个元素，默认能达到
if(nums.size()==1){
return 0;
}
// i 每次只能在cover的范围内移动
int result = 0;
int curCover=0; // 当前这一步的覆盖范围的最远下标
int nextCover=0;// 下一步的覆盖范围的最远下标
//循环移动
for(int i=0;i<nums.size();i++){
nextCover = max(i+nums[i],nextCover);//更新最大覆盖范围
//如果走到当前这一步的覆盖范围的终点
if(i==curCover){
// 如果不是数组终点
if(i!=nums.size()-1){
result++;//步数+1
curCover=nextCover;//更新当前步数的范围
// 如果下一步范围覆盖了终点则直接返回
if(curCover>=nums.size()-1){
break;
}
}else{
break;
}
}
}
return result;
}
134. 加油站（中等难度）
/*从本题的题目中首先要读懂两个设定：
-如果可以跑完全程,这个起始站点是唯一的，不可能存在从多个起始站点出发都可以跑完全程的情况
（题目说明中存在“如果题目有解，该答案即为唯一答案”）；
-如果不可以跑完全程,说明其耗油总量（cost数组元素之和）一定大于加油总量（gas数组元素之和）。
然后可以知道：从第i个站点出发跑到下一站点加油前，其加油gas[i],耗油cost[i]，
相当于第i个站点给车贡献了res[i]=gas[i]-cost[i]的油量。
那么可以假设车子从第i=0个站点出发，然后到达第i+1个站点加油前的油量为curSum=res[0]+...+res[i];
如果此时curSum<0，说明车子无法达到第i+1个站点，
同时细想下我们也发现[0,j]中任何一个站点出发都不会走完全程了，因为从第0个站点走到第j+1都不够，
那车子从第1个站点走到第j+1更不可能了，因为加油的站点更少了，所以出发站点只能在第j+1之后了
*/
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start=0; // 起始站点
int curSum = 0; // 当前车子中的油量
int totalSum = 0; // 全程一圈的总油量
for(int i=0;i<gas.size();i++){
// 从i站点出发获得的油量
curSum+=gas[i]-cost[i];
//车子没油了,说明[0,i]都不可以作为起始站点
if(curSum <0){
start=i+1;//更换起始站点
curSum = 0;
}
totalSum+=gas[i]-cost[i];//记录当前站点可以获得的油量
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
return start;
}
452. 用最少数量的箭引爆气球（中等难度）
当气球出现重叠，一起射，所用弓箭最少；那么，把所有气球射爆的所用弓箭一定最少。
解答本题需要一些编程技巧，首先将气球排序，可以不删除气球数组通过遍历就能计算所用弓箭。
可以按照气球的起始位置排序，也可以按照气球的终止位置排序；
然后比较当前气球和前一个气球是否重合，不重合增加一只箭，重合则更新当前气球的右边界（取当前气球右边界和前一个气球右边界的最小值）；
当前思路示意图如下：
按照气球的起始位置排序的代码如下：
class Solution {
public:
/* 贪心算法：全局最优：把所有气球射爆所用弓箭最少
局部最优：当气球出现重叠，一起射，所用弓箭最少；
首先将气球排序，可以不删除气球数组通过遍历就能计算所用弓箭。
可以按照气球的起始位置排序，也可以按照气球的终止位置排序；
然后比较当前气球和前一个气球是否重合，不重合增加一只箭，
重合则更新当前气球的右边界（取当前气球右边界和前一个气球右边界的最小值）
*/
// 按照起始位置从小到大排列
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
/*输入一个二维数组（气球直径），返回一个整数（最小弓箭数）*/
if(points.size()==1) return 1;
// 首先按照气球的起始位置排序
sort(points.begin(),points.end(),cmp);
int res=1;//至少有一个气球，所以至少需要一支箭
for(int i=1;i<points.size();i++){
// 如果前一个气球的右边界>当前气球的左边界,说明两个气球不重合
if(points[i-1][1]<points[i][0]) res++;
// 当两个气球重合时,重新定义当前气球的右边界
else points[i][1]=min(points[i-1][1],points[i][1]);
}
return res;
}
};
注意：
cmp的参数传入最好设置为引用，因为不使用引用的话，排序过程中每次通过直接赋值到形参会造成大量的时间浪费
435. 无重叠区间（中等难度）
这道题目和（452 用最少数量的箭引爆气球）非常像，同样先将二维数组按照第二维数组的起点从小到大排序
然后比较当前区间的左边界和前一个区间的右边界来判断是否重叠，没有重叠跳过去，重叠了则结果+1，并且将当前区间的右边界取最小值（相当于默认删除右边界区间较大的那个重叠区间）
代码如下：
static bool cmp(vector<int>& a,vector<int>& b){
return a[0]<b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
/*输入一个二维数组，返回一个整数*/
if(intervals.size()<=1) return 0;
int res=0;
// 将二维数组按照第二维数组的起点从小到大排序
sort(intervals.begin(),intervals.end(),cmp);
for(int i=1;i<intervals.size();i++){
// 如果相邻区间没有重叠
if(intervals[i-1][1]<=intervals[i][0])continue;
// 如果相邻区间重叠,则重新定义当前区间的右边界，取最小值
//（相当于默认删除右边界区间较大的那个区间），
else {
res++;
intervals[i][1] = min(intervals[i-1][1],intervals[i][1]);
}
}
return res;
}
763. 划分字母区间（中等难度）
接下来就是代码：
class Solution {
public:
/*该题目就是分割字符串，将同一个字母都圈在一个区间里。
其等价于找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界
说明这个边界就是分割点
所以我们可以遍历两次字符串，
- 第1次遍历统计每个字符出现的最后位置；
- 第2次遍历寻找分割点（字符最远下标与当前下标相等）*/
vector<int> partitionLabels(string s) {
// 统计每个字符出现的最后位置
int feq[27]={0};//字母频率数组
for(int i=0;i<s.size();i++) feq[s[i]-'a']=i;
// 遍历字符串寻找分割点
vector<int> res;
int left = 0;
int right = 0;
for(int i=0;i<s.size();i++){
// 当前字符最远边界和之前字符的最远边界的最大值
right = max(right, feq[s[i] - 'a']);
//如果当前位置是最远距离则是分割点
if(i==right){
res.push_back(right-left+1);//计算该长度
left=i+1;//更新左边界
}
}
return res;
}
};
56. 合并区间（中等难度）
class Solution {
public:
/*该题目就是合并区间，需要注意一点的是两个相邻区间合并后的新区间可能还和之后的区间需要合并，
所以说明了可能连续n个区间可以合并在一起。这个n是不确定的，所以我们需要一个二重循环:
外层负责遍历两个相邻区间，内层负责判断是否是否重叠，重叠了则合并边界将其加入结果。
合并只需要排序，确保遍历时每个不重叠的区间的左边界始终是最小的，不断更新右边界即可*/
// 按照区间左边界从小到大排序
static bool cmp(const vector<int>& a,const vector<int>& b){
return a[0]<b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==1) return intervals;
// 将数组排序
sort(intervals.begin(),intervals.end(),cmp);
vector<vector<int>> res;
int start=0;
int end=0;
bool flag = false; // 标记最后一个区间有没有合并
// 遍历每个区间
for(int i=1;i<intervals.size();i++){
start = intervals[i-1][0]; // 初始为i-1区间的左边界，一定是最小的，因为排序了
end = intervals[i-1][1]; // 初始i-1区间的右边界，不一定是最大的，重叠时需要更新
// 如果i区间和i-1区间重叠（需要保证i没有出界）
while (i<intervals.size() &&end>=intervals[i][0]) { // 合并区间
end=max(end,intervals[i][1]); // 更新右区间
if (i == intervals.size() - 1) flag = true; // 如果最后一个区间也发生重叠则标记下
i++; // 继续合并下一个区间
}
res.push_back({start,end});
}
// 如果最后一个区间没有和前一个区间重叠，将需单独加入result
if (flag == false) {
res.push_back({intervals[intervals.size() - 1][0], intervals[intervals.size() - 1][1]});
}
return res;
}
};
五、权衡问题
406. 根据身高重建队列（中等难度）
本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后在按照另一个维度重新排列。
按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
那么只需要按照k为下标重新插入队列就可以了，为什么呢？
以图中{5,2} 为例：
代码如下：
class Solution {
public:
/*本题有两个维度:h和k，一定要想如何确定一个维度，然后按照另一个维度重新排列。
按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
那么只需要按照k为下标重新插入队列就可以了*/
static bool cmp(vector<int> &a,vector<int> &b){
// 如果身高相同则按照k从小到大排列
if(a[0]==b[0]){
return a[1]<b[1];
}
return a[0]>b[0];//默认将身高按照从大到小排列
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
/*输入一个二维数组，输出一个二维数组*/
sort(people.begin(),people.end(),cmp);
vector<vector<int>> que;
// 按照k调整队列
for (int i = 0; i < people.size(); i++) {
int position = people[i][1];
que.insert(que.begin() + position, people[i]);
}
return que;
}
};
按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。
所以使用vector（动态数组）来insert，是费时的
135. 分发糖果（困难难度）
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1);//糖果数组，默认都先有1个
// 从前向后遍历孩子，如果后一个孩子i评分更好,为其多添加一个糖果
for(int i=1; i<ratings.size();i++) {
if(ratings[i]>ratings[i-1]) candyVec[i]=candyVec[i-1]+1;
}
// 从后向前遍历孩子，如果前一个孩子i评分更好：
// candyVec[i]必须比左边的candyVec[i-1]和右边的candyVec[i+1]都大
for (int i = ratings.size() - 2; i >= 0; i--) {
if(ratings[i]>ratings[i+1]) {
//candyVec[i]=candyVec[i+1]+1;// 其+1可能比原来的值小,从而比左孩子少
candyVec[i]=max(candyVec[i], candyVec[i+1]+1);
}
}
// 统计结果
int res = 0;
for (int i = 0; i < candyVec.size(); i++) res += candyVec[i];
return res;
}
};
621. 任务调度器（中等难度）
class Solution {
public:
/*完成所有任务的最短时间取决于出现次数最多的任务数量
因为相同任务之间不能连续执行，有冷却时间
所以需要把出现次数最多的任务先安排上
范例["A","A","A","B","B","B"], n = 2
出现频率最多的任务是A和B，其频率为3，
则最多任务频率m=3，最多任务个数x=2
1、当任务种类数比较少时：
int opt_1=(m-1)*(n+1)+x=（3-1）*(2+1)+2=8
2、当任务种类数比较多时：
int opt_2=tasks.size()
最终结果：res=max(opt_1, opt_2)*/
static bool cmp(pair<char,int>&a, pair<char,int>&b){
return a.second>b.second;
}
int leastInterval(vector<char>& tasks, int n) {
int len=tasks.size();
if(len==1) return 1;
// 统计每个任务出现的次数
unordered_map<char, int> dict;
for (char task : tasks) dict[task]++;
// 按任务出现的次数从大到小排序
vector<pair<char,int>> arr;
for(auto iter:dict) arr.push_back(make_pair(iter.first,iter.second));
sort(arr.begin(),arr.end(),cmp);
// 出现频率最大的任务频率和任务数量
int m = arr[0].second; // 出现最多次任务的次数
int x = 0; // 任务数量最多的任务的种类数量
for(auto iter:arr) if(iter.second==m) x++;
// 方案一：
int opt_1 = (m-1)*(n+1)+x;
// 方案二：所有任务的数量
int opt_2 = len;
return max(opt_1, opt_2);
}
};