贪心算法（greedy algorithm）基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。 贪心思路的本质，如果找不到重复计算，那就通过问题中一些隐藏较深的规律，来减少冗余计算。
从局部最优推导出全局最优，但是有时局部最优并不一定能导出全局最优（比如背包问题） 而贪心算法的关键点是：无套路。因此本博文仅仅是总结一些贪心算法相关的例题。 实际做题时，需要根据题目的特点，来判断是否适合使用贪心算法。可从下面三个方向思考：
-
每步的局部最优是什么？
-
能否推导出全局最优？
-
是否有反例这样做无法得到最优解？
贪心算法与动态规划区别：零钱兑换（背包问题）
相同点在于都是解决优化问题的，也依赖最优子结构的性质。但是工作原理不一样~。
- 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
- 贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。
在动态规划博客Link中，介绍过完全背包问题的兑零钱的解法。
贪心算法的解法。在此代码中，假设最小面值为min，那么时间复杂度应该是O（amount/min）比起背包问题的动态规划解法时间复杂度O（n*amount）少不小。但是对于某些硬币面值组合，贪心算法并不能找到最优解（在leeetcode上测试并无法通过所有的样例）因此，贪心算法并不能用于解决背包问题，背包问题只能用动态规划去解决~。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
//首先需要保证coins是有序的
sort(coins.begin(),coins.end());
int i=coins.size()-1;//当前面值最大的硬币的索引
int count = 0;//初始化需要的最小硬币数为0；
//循环进行贪心选择，直到没有剩余金额
while(amount>0)
{
// 找到小于且最接近剩余金额的硬币
while(i>0 && coins[i]>amount)
{
i--;
}
// 选择这个硬币
amount-=coins[i];
count++;
}
// 若未找到可行方案，则返回 -1
return amount==0? count:-1;
}
};
用完全背包问题思路的动态规划解法~
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
int MAX = amount + 1;//最大的硬币数目
//step1: 定义 dp 表：dp[i][j]=前种硬币能够凑出金额的最少硬币数量
// 状态：i中物品，当前的金额数
// 选择：用或者不用当前面值的硬币
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
// step2:初始化状态：对于硬币数为0，但是需要的金额数不为0的情况，凑不到了为此质为0
for (int a = 1; a <amount+1; a++) {
dp[0][a] = MAX;//当前没有硬币了，为此是最大的
}
//对于其他情况，比如需要金额为0，那么最小的金币数也是0，已经初始化了~
// step3，进行状态转移
for (int i = 1; i <n+1; i++) {
for (int a = 1; a <amount+1; a++) {
if (coins[i - 1] > a) {
// 若超过目标金额，则不选硬币 i
dp[i][a] = dp[i - 1][a];
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = min(
dp[i - 1][a], //不选择
dp[i][a - coins[i - 1]] + 1);//选择的最小值
}
}
}
return dp[n][amount] != MAX ? dp[n][amount] : -1;
}
};
一维动态规划解法
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// step1:定义dp表，代表对于需要的金额i，dp【i】状态为[最少的硬币个数]
vector<int> dp(amount+1, 0);//当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出
// step2:确定初始状态，当总金额为0的时候，最小的硬币数量为0
dp[0]=0;
// step3：进行状态转移
for(int i=1;i<amount+1;i++)//遍历所有状态的所有取值
{
//由于每轮是要选最值的，故此必须先初始化！
dp[i]=amount+1;//每一轮对其进行初始化，初始化为每个面值为1元的硬币+1，那么就是最大的。也是全部的最大
for(auto each_coin:coins)//选择对应的面值
{
if(i-each_coin<0)//剪枝，当前硬币面值太大了
continue;
else
dp[i]=min(dp[i],dp[i-each_coin]+1);//不选这个面值，或者选这个面值，两种情况的最小
}
}
if(dp[amount]==amount+1)//没有面值合适,故此没有发生变化～
return -1;
else
return dp[amount];
}
};
因此，对于零钱兑换问题，贪心算法无法保证找到全局最优解。它更适合用动态规划解决。
一般情况下，贪心算法的于以下两种。
- 可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效。
- 可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错的。
要保证上面两种情况，一般问题需要满足以下两个条件：
- 贪心选择性质：一个问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
- 最优子结构性质：原问题的最优解包含子问题的最优解。
分数背包问题
此题跟 0-1 背包问题整体上非常相似，状态包含当前物品和容量，目标是求限定背包容量下的最大价值。 不同点在于，本题允许只选择物品的一部分。我们可以对物品任意地进行切分，并按照重量比例来计算相应价值。 如下图所示。
为此可以采用贪心算法，按照单位重量价值从大到小排序，然后依次选择：
1.将物品按照单位价值从高到低进行排序。
2.遍历所有物品，每轮贪心地选择单位价值最高的物品。
3.若剩余背包容量不足，则使用当前物品的一部分填满背包。
时间与空间的复杂度都为O（N）
/* 物品 */
class Item {
public:
int w; // 物品重量
int v; // 物品价值
Item(int w, int v) : w(w), v(v) {
}
};
/* 分数背包：贪心 */
double fractionalKnapsack(vector<int> &wgt, vector<int> &val, int cap) {
// 创建物品列表，包含两个属性：重量、价值
vector<Item> items;
for (int i = 0; i < wgt.size(); i++) {
items.push_back(Item(wgt[i], val[i]));
}
// 按照单位价值 item.v / item.w 从高到低进行排序
sort(items.begin(), items.end(), [](Item &a, Item &b) { return (double)a.v / a.w > (double)b.v / b.w; });
// 循环贪心选择
double res = 0;//最终的价值
for (auto &item : items) {
if (item.w <= cap) {
// 若剩余容量充足，则将当前物品整个装进背包
res += item.v;//价值递增
cap -= item.w;//重量递减
}
else {
// 若剩余容量不足，则将当前物品的一部分装进背包
res += (double)item.v / item.w * cap;
// 已无剩余容量，因此跳出循环
break;
}
}
return res;
}
最大容量问题
时间复杂度为O(N),空间复杂度为O（1）。贪心算法比穷举更快，是因为每轮的贪心选择都会“跳过”一些状态。从而导致一些状态无法被验证。但是通过代码分析可以发现跳过的这些状态都必然不是最优解，故此跳过他们可以加速同时不影响最终结果
/* 最大容量：贪心 */
int maxCapacity(vector<int> &ht) {
// 初始化 i, j，使其分列数组两端
int i = 0, j = ht.size() - 1;
// 初始最大容量为 0
int res = 0;
// 循环贪心选择，直至两板相遇
while (i < j) {
int cap = min(ht[i], ht[j]) * (j - i);//当前的容量
res = max(res, cap);// 更新最大容量
// 向内移动短板：
if (ht[i] < ht[j]) {
//若i为短板，j--的话，容量必然减少，因此只能i++，才有可能增加容量
i++;
} else {
//同理，若j为短板，i++的话，容量必然减少，因此只能j--，才有可能增加容量
j--;
}
}
return res;
}
分发饼干
,时间复杂度为O(nlogn)，空间复杂度为O（1）
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
// 局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，
// 全局最优就是喂饱尽可能多的小孩。
//进行从大到小的排序，先优先喂饱最大的，然后统计数量
int count=0;//喂饱的数量
sort(g.begin(),g.end(),greater<int>());//小孩胃口
sort(s.begin(),s.end(),greater<int>());//饼干尺寸
int index=0;//饼干的索引（没必要采用两个for循环，但是注意需要处理越界的情况）
for(int i=0;i<g.size();i++)//遍历所有的小孩
{
if(index>=s.size())//注意double check 索引是否越界！
break;
if(s[index]>=g[i])
{
count++;//喂饼干的数量+1
index++;//喂完当前饼干了，索引自加
}
}
return count;
}
};
既可动态规划，又可贪心算法
根据这类题目的分析，可以发现，其实不少贪心算法都可以用动态规划算法Link解决。当然动态规划算法是成套路的。而贪心算法则是可以更快的解题。同时也可以通过部分的测试案例（最佳的情况，或者说符合贪心算法标准就是通过100%）
摆动序列
（动态规划解法）
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
//采用动态规划
//step1:定义dp表
int up[nums.size()];//从0开始，对于位置为i，最长上升摆动序列
int down[nums.size()];//从0开始，对于位置为i，最长的下降摆动序列
// step2：初始化dp表。对于只有一个元素的情况也是摆动序列
up[0]=1;
down[0]=1;
for(int i=1;i<nums.size();i++)
{
if(nums[i]>nums[i-1])//当前i大于上一个值
{
//删除这个值对应的i-1时最长上升摆动序列。与，i-1时最长的下降摆动序列+1成为上升序列
up[i]=max(up[i-1], down[i-1]+1);
down[i]=down[i-1];//上一个是波谷的话，当前值只能删除，为此只等于上一个状态
}
else if(nums[i]<nums[i-1])//当前i小于上一个值
{
// 跟上面反过来
down[i]=max(down[i-1], up[i-1]+1);
up[i]=up[i-1];
}
else//相等的情况
{
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return max(up[nums.size()-1],down[nums.size()-1]);//两者的最大值
}
};
贪心算法直接统计每次结果，从局部的值推导全局值
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
//直接统计
int result=1;//初始化为1，只有一个数的时候也算，而第一次只要两者不相等，就算2了
int cur=0, last=0;
for(int i=1;i<nums.size();i++)
{
if(nums[i]==nums[i-1])//相等时忽略
{
continue;
}
else if(nums[i]>nums[i-1])
cur=1;//上升
else
cur=-1;//下降
if(cur!=last)//若跟上一次差值不同，就是一个波峰或者波谷
result++;
last=cur;//更新上一次的值
}
return result;
}
};
最大子数组和
动态规划解法。时间复杂度为O（N），空间复杂度为O（N）
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//step1：定义dp表：dp[i]=索引为i的数字,能获取的最大和
//状态：对于索引为i的数字
//选择：从当前索引重新开始或用之前累计的结果
int dp[nums.size()];
//step2:初始化dp表
dp[0]= nums[0];//第一个的最大值就是第一个数
// step3:进行状态转移
int result=dp[0];//记录全部的最大值(注意，此处不能用INT_MIN,需要初始化为第一个数组)
for(int i=1;i<nums.size();i++)
{
// 从当前索引从新算，或者当前+上一个状态
dp[i]=max(nums[i],dp[i-1]+nums[i]);
result=max(dp[i],result);
}
return result;
}
};
贪心算法的解法，当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。时间复杂度为O（N），空间复杂度为O（1）
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result=INT_MIN;//注意要初始化为最小的负数，因为可能一开始就为负数
int temp_sum=0;
for(int i=0;i<nums.size();i++)
{
temp_sum+=nums[i];
result=max(temp_sum,result);//每次加完后,记录最大值（最终作为全局最优）
// 当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，
// 因为负数加上下一个元素 “连续和”只会越来越小。
if(temp_sum<0)//为负数了，马上重置
temp_sum=0;
//注意遇到负数后，继续加和，下一个可能更大（和为正，对下一个必然是增大的作用）。
//但是和为负数后，如果继续加下一个必然更小。
// 为此应该选和为负的时候作为零界点
}
return result;
}
};
K次取反后最大化的数组和
时间复杂度为O(Nlogn)，空间复杂度为O（1）
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
// 局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
sort(nums.begin(),nums.end());//进行排序（也可以改为按照绝对值大小排序）
int index=0;//数组的索引
while(k>0)
{
//优先将绝对值最大的负数转换为正数
if(nums[index]<0)
{
nums[index]=-nums[index];
index++;
k--;
if(index>=nums.size())//数组遍历完了（注意凡是非for的数组遍历都需要double check）
{
break;
}
}
else
{
break;//剩下的都是正数了
}
}
if(k>0)//还有k可以继续转换
{
//若全部负数都转换为正数了，还有k则应该多次只转换最小的一个数
sort(nums.begin(),nums.end());//再次排序,从小到大
while(k>0)
{
nums[0]=-nums[0];
k--;
}
}
//获取最终结果
int result=0;
for(int i=0;i<nums.size();i++)
{
result+=nums[i];
}
return result;
}
};
加油站
局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。（注意题目说了如果有解，必然是唯一解）
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
//到达加油站i可以获得gas[i]油，离开加油站i需要消耗cost[i]
// 返回从哪个站出发可以绕一圈，若没有则输出-1
//首先需要基于如下结论：
// 如果选择站点 i 作为起点「恰好」无法走到站点 j，那么 i 和 j 中间的任意站点 k 都不可能作为起点。
int sum=0;
for(int i=0;i<gas.size();i++)
{
sum+=gas[i]-cost[i];//总油量小于0，那么必然无法跑一圈
}
if(sum<0)
return -1;//总剩余的油量小于0，那么必然无解
// 否则就必然有解，但题目保证了解是唯一的！！！
int index=0;//记录起点
int temp_sum=0;
for(int i=0;i<gas.size();i++)
{
temp_sum+=gas[i]-cost[i];//当前的油量
if(temp_sum<0)//(上次的i到当前都必然不是结果)
{//另外一种思维，当前已经是不满足了，那么就尝试从下一刻出发！然后再次计算
temp_sum=0;//清空
index=i+1;//起点至少是i+1，因为从i之前开始一定不行，然后继续验证
}
}
return index==gas.size()? 0:index;//为n时，正好绕一周所以是从0开始
}
};
柠檬水找零
，模拟算法计数器。时间复杂度为O（N），空间复杂度为O（1）.但这其实也是算贪心算法！！！
局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。 局部最优可以推出全局最优，因为每次找零都是最优的，那么最终的找零也是最优的。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {//注意题意必须按账单bilis支付顺序
// 定义三个计数器
int count_5=0;
int count_10=0;
int count_20=0;
for(int i=0;i<bills.size();i++)
{
if(count_5<0 || count_10<0)
return false;
if(bills[i]==5)
count_5++;
else if(bills[i]==10)
{
count_10++;
count_5--;
}
else
{
if(count_10>0)
{
count_10--;
count_5--;
}
else//若没有10块，找三张5块
count_5=count_5-3;//或者减三也可以
count_20++;
}
}
if(count_5<0 || count_10<0)
return false;
return true;
}
};
两次贪心策略：分发糖果
,时间与空间复杂度O（N）。
确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
先确定右边评分大于左边的情况（也就是从左向右遍历）此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。（局部最优可以推出全局最优）
再确定左孩子大于右孩子的情况（也就是从右向左遍历）
特殊情况：某个值既大于它的左边，又大于它的右边。也就是candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。
class Solution {
public:
int candy(vector<int>& ratings) {
//贪心算法
vector<int> candyVec(ratings.size(), 1);//每个孩子至少分配到 1 个糖果。
// 先从左到右对比
for(int i=1; i<ratings.size(); i++)
{
if(ratings[i]>ratings[i-1])//(若有右比左大的情况，ratings[i]要更大)
candyVec[i]=candyVec[i-1]+1;//每两个有一个更大就应该+1
}
//然后从右到左对比
for(int i=ratings.size()-1;i-1>=0;i--)
{
if(ratings[i]<ratings[i-1])//(若有左比右大的情况，candyVec[i-1]要更大)
candyVec[i-1]=max(candyVec[i-1],candyVec[i]+1);//每两个有一个更大就应该+1(但若原本已经是更大的状态，就无需再加)
//因为若原本此处右大于左时加了糖果，更大了。此时它为与左，比它的右也大，则无需再+1
}
int result = 0;//最终结果
for (int i = 0; i < candyVec.size(); i++)
result += candyVec[i];
return result;
}
};
根据身高重建队列
遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。但是题目关键应该还是如何确定排序的方法，要先按什么排序，再按什么排序！
空间复杂度为O（N），时间复杂度为O（N2）因为用了vector的insert操作，为此时间复杂度并不是O（N）。sort的时间复杂度为O（NlogN）。
class Solution {
public:
static bool comparefunction(vector<int>& a, vector<int>& b)
{
if(a[0]!=b[0])
return a[0]>b[0];
else
return a[1]<b[1];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
// 局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
// 全局最优：最后都做完插入操作，整个队列满足题目队列属性
//第一个是身高，第二个是前面有k个大于等于当前身高的值
//先按身高从大到小排序（身高相同的情况下，按照k值从小到大排序）
sort(people.begin(),people.end(),comparefunction);
vector<vector<int>> result;
for(int i=0;i<people.size();i++)
{
//当前身高，前面有几个大于等于当前身高的值,对应就插入result.begin()+position的位置
int position = people[i][1];//前面应该有多少值，因此位于第几个
result.insert(result.begin()+position,people[i]);//对应的位置插入
}
return result;
}
};
判断区间重叠
跳跃游戏
（问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！）贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
class Solution {
public:
bool callback(vector<int>& nums, int index)
{//初始化的时候位于第一步
// 递归终止条件
if(index==nums.size()-1)
{
// 当正好跳到终点
return true;
}
int next_step=nums[index];//下次可以跳的最大的步数
if(next_step<=0)
return false;
//若没有超出数组范围就是index+next_step
int max_target=(index+next_step)<nums.size()-1? next_step:(nums.size()-1-index);
for(int i=1;i<=max_target;i++)
{
if(callback(nums, index+i))
{//有一个结果到了终点就马上返回true
return true;
}
}
return false;//遍历全部后
}
bool canJump(vector<int>& nums) {
// return callback(nums,0);//采用递归(容易超时)
//为此采用贪心算法
int mostright=0;//记录当前最远的可以到的右侧的距离
for(int i=0;i<nums.size();i++)
{
if(i<=mostright)//当前i最大也只能到mostright
{
mostright=max(mostright,i+nums[i]);
//跳多少步无关系，关键是最远能否到达终点
if(mostright>=nums.size()-1)
return true;
}
}
// 否则就是永远不可能到达
return false;
}
};
解题的关键在于什么情况下步数+1.局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
class Solution {
public:
int jump(vector<int>& nums) {
int count=0;//由于按题目说，必然可以达到目标点，为此符合贪心算法
//注意是跳跃次数
int right_most=0;//记录当前最远的可以到的右侧的距离
int cur_end=0;//当前跳跃能够到达的最大下标位置
for(int i=0;i<nums.size();i++)
{
right_most=max(right_most,i+nums[i]);//当前最右侧
// 先检查当前i是否已经到达了最后一个位置
if(i==nums.size()-1)
break;
//i通过自增，进而获取i后面每个位置可以调的最大目的地
//当达到当前跳跃的边界时
if (i == cur_end) {
count++; //达到第一次目的地，就增加跳跃次数
// 更新下次跳跃可以到达的最大边界
cur_end = right_most; //上一个i到它的 cur_end所有的点中，最远可以跳到的地方
}
}
return count;
}
};
用最少数量的箭引爆气球
关键在于需要更新右边界，不能单纯对比，因为必须满足每个最小右边界能被碰到！
class Solution {
public:
static bool comparefunction(vector<int> &a, vector<int> &b)
{
if(a[0]!=b[0])
return a[0]<b[0];
else
return a[1]<b[1];
}
int findMinArrowShots(vector<vector<int>>& points) {
//先进行排序
sort(points.begin(),points.end(),comparefunction);
int result=1;//一开始是一枝箭
for(int i=1;i<points.size();i++)
{
//如果两个气球有交集
if(points[i][0]<=points[i-1][1])//当前的左边界<=上一个的右边界
{
points[i][1]=min(points[i-1][1],points[i][1]);//更新重叠的气球的最小右边界，下次与最小右边界对比
}
else
result++;//要多加一支箭
}
return result;
}
};
无重叠区间
按照左边界排序。时间复杂度：O(nlog n) ，有一个快排。空间复杂度：O(n)，有一个快排，最差情况(倒序)时，需要n次递归调用。因此确实需要O(n)的栈空间
class Solution {
public:
static bool comparefunction(vector<int>& a, vector<int>& b)
{
return a[0]<b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
// 此题有点类似于452：用最少数量的箭引爆气球
// 先进行排序
sort(intervals.begin(),intervals.end(),comparefunction);//按照左边界排序
int result=0;
for(int i=1;i<intervals.size();i++)
{
if(intervals[i][0]>=intervals[i-1][1])//若当前的左边界大于等于上一个右边界，那么没有重叠
{
continue;
}
else//必然有重叠
{
result++;
// 由于当前是去除掉的，为此更新一下值(下一个会用此来做对比)
//右边界记录最小值（这个可以确定去掉大的边）
intervals[i][1]=min(intervals[i][1], intervals[i-1][1]);
}
}
return result;
}
};
若按照右边界排序，本质上好像是一样的，只是左边界排序个人感觉更好理解~
class Solution {
public:
static bool comparefunction(vector<int>& a, vector<int>& b)
{
return a[1]<b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
// 此题有点类似于452：用最少数量的箭引爆气球
// 先进行排序
sort(intervals.begin(),intervals.end(),comparefunction);//按照右边界排序
int result=0;
for(int i=1;i<intervals.size();i++)
{
if(intervals[i][0]>=intervals[i-1][1])//若当前的左边界大于等于上一个右边界，那么没有重叠
{
continue;
}
else//必然有重叠
{
result++;
// 由于当前是去除掉的，为此更新一下值(下一个会用此来做对比)
//右边界记录最小值（这个可以确定去掉大的边）
// intervals[i][1]=min(intervals[i][1], intervals[i-1][1]);
intervals[i][1]= intervals[i-1][1];//上一行写法也可，因为右边界已经排序了！！！
}
}
return result;
}
};
划分字母区间
时间复杂度O（N），空间复杂度O（1）
class Solution {
public:
vector<int> partitionLabels(string s) {
// 每个字母最多出现在一个片段中。（就是说相同的字母必须在同一个片段中，且不能改变顺序）
//循环遍历过的所有字母的最远边界，这个就是分割点，放入result中
vector<int> result;
//先统计每个字符最后出现的位置
unordered_map<char, int> hash_table;
for(int i=0;i<s.size();i++)
{
hash_table[s[i]]=i;//记录index
}
int right_most=0;
int curret_startindex=0;
//从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
for(int i=0;i<s.size();i++)
{
//此时的right_most为当前curret_startindex遍历的最远的
right_most=max(right_most,hash_table[s[i]]);//当前字符最远的
if(i==right_most)//当前字符串到达了最远
{
result.push_back(right_most-curret_startindex+1);//片段的长度
curret_startindex=i+1;//从下一个开始算
}
}
return result;
}
};
合并区间
解题思路跟上面几题是很像的。时间复杂度: O(n+nlogn)。空间复杂度: O(logn)，排序需要的空间开销
class Solution {
public:
static bool comparefunction(vector<int>& a, vector<int>& b)
{
return a[0]<b[0];//按左区间从小到大排列
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
//先进行排序
sort(intervals.begin(),intervals.end(),comparefunction);
vector<vector<int>> result;
int new_left;
int new_right;
for(int i=1;i<intervals.size();i++)
{
if(intervals[i-1][1]>=intervals[i][0])//当前的左区间小于等于上一个右区间，有重叠
{
intervals[i][0]=min(intervals[i-1][0],intervals[i][0]);//最小值
intervals[i][1]=max(intervals[i-1][1],intervals[i][1]);//最大值
// 下次继续对比
}
else//没重叠，就push
{
result.push_back(intervals[i-1]);//将上一次的放入
}
}
//把最后一个也放入
result.push_back(intervals[intervals.size()-1]);
return result;
}
};
单调递增的数字
时间与空间复杂度都为O（N）
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string input_str=to_string(n);//转换为string
int index=input_str.size();//从第几个开始应该全部变为9
// （初始化为input_str.size()取不到，不初始化的话会直接导致从0开始之后全部变为9）
for(int i=input_str.size()-1;i>=1;i--)
{
if(input_str[i-1]>input_str[i])//前一个大于后一个了
{
index=i;//记录从第几个开始应该全部为9
input_str[i-1]=input_str[i-1]-1;//当前位应该减一，然后当前位置的下一个应该为9（比如对于66，56<59）
}
}
//从第几个开始应该全部变为9(9绝对是当前能到的最大的)
for(int i=index;i<input_str.size();i++)
{
input_str[i]='9';
}
return stoi(input_str);
}
};
监控二叉树
从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！由于采用先从叶节点向上找，为此是后续历遍。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int result=0;//定义全局变量为摄像头数目
//返回的为节点的状态。定义三种状态：0（节点无覆盖），1（节点有摄像头），2（节点有覆盖）
int traversal(TreeNode* current)
{
//到达根节点，那么就是当前是空节点，那么必须是有覆盖的（但同时不能是有摄像头）
if(current==nullptr)
return 2;
int left=traversal(current->left);//获取左边节点的状态
int right=traversal(current->right);//获取右边节点的状态
// 后续历遍
//若左边跟右边都有覆盖
if(left==2 && right==2)
return 0;//不能放摄像头
//若左边或右边没有覆盖，那就必须有一个摄像头（当前）
else if(left==0 || right==0)
{
result++;
return 1;//当前必须放摄像头
}
//若左边或右边有摄像头
else if(left==1 || right==1)
return 2;//当前是覆盖的
return -1;//此处是不会执行的
}
int minCameraCover(TreeNode* root) {
//示例中的摄像头都没有放在叶子节点上！
// （摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。）
//因此，从叶节点开始，把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
//由于采用先从叶节点向上找，为此是后续历遍
if (traversal(root) == 0) { // 若当前头节点返回的结果是无覆盖，那么头节点处还需放一个摄像头！
result++;
}
return result;
}
};