- 1、贪心算法理论基础
- 2、分发饼干
- 3、摆动序列
- 4、最大子序和
- 5、贪心周总结
- 6、买卖股票的最佳时机 II
- 7、跳跃游戏
- 8、跳跃游戏 II
- 9、K次取反后最大化的数组和
- 10、贪心周总结
- 11、加油站
- 12、分发糖果
- 13、柠檬水找零
- 14、根据身高重建队列
- 15、贪心周总结
- 16、根据身高重建队列（vector原理讲解）
- 贪心算法：根据身高重建队列(opens new window)中，我们提到了使用vector（C++中的动态数组）来进行insert操作是费时的。
但是在解释的过程中有不恰当的地方，所以来专门写一篇文章来详细说一说这个问题。
使用vector的代码如下：">贪心算法：根据身高重建队列（续集）
在讲解贪心算法：根据身高重建队列(opens new window)中，我们提到了使用vector（C++中的动态数组）来进行insert操作是费时的。
但是在解释的过程中有不恰当的地方，所以来专门写一篇文章来详细说一说这个问题。
使用vector的代码如下： - 17、用最少数量的箭引爆气球
- 18、无重复区间
- 19、划分字母区间
- 20、合并区间
- 21、贪心周总结
- 22、单调递增的数字
- 23、买卖股票的最佳实际含手续费
- 24、监控二叉树（困难）
- 25、贪心算法总结篇
1、贪心算法理论基础
1.1、什么是贪心
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
1.2、贪心的套路（什么时候用贪心）
很多同学做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优，推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？
不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢？
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。
一般数学证明有如下两种方法：
- 数学归纳法
- 反证法
看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。
面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。
举一个不太恰当的例子：我要用一下1+1 = 2，但我要先证明1+1 为什么等于2。严谨是严谨了，但没必要。
虽然这个例子很极端，但可以表达这么个意思：刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！
所以这也是为什么很多同学通过（accept）了贪心的题目，但都不知道自己用了贪心算法，因为贪心有时候就是常识性的推导，所以会认为本应该就这么做！
那么刷题的时候什么时候真的需要数学推导呢？
例如这道题目：链表：环找到了，那入口呢？(opens new window)，这道题不用数学推导一下，就找不出环的起始位置，想试一下就不知道怎么试，这种题目确实需要数学简单推导一下。
1.3、贪心一般解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。
2、分发饼干
思路
这里的局部最优就是大饼干喂给胃口大的，充分利用每一个饼干的尺寸喂饱每一个孩子，全局最优就是喂饱尽可能多的小孩。
或者是 这里的局部最优就是小饼干喂给胃口小的。
这道题很容易，直接给代码了
大饼干喂给胃口大的
class Solution {public:int findContentChildren(vector<int>& g, vector<int>& s) {std::sort(g.begin(), g.end()); // 将孩子的胃口值进行从小到大的排序std::sort(s.begin(), s.end()); // 将饼干的尺寸进行从小到大的排序int count = 0; // 记录得到满足的小孩for(int i = g.size() - 1, j = s.size() - 1; i >= 0 && j >= 0;){if(s[j] >= g[i]){count++;i--;j--;}else{i--;}}return count;}};
小饼干喂给胃口小的
class Solution {public:int findContentChildren(vector<int>& g, vector<int>& s) {std::sort(g.begin(), g.end()); // 将孩子的胃口值进行从小到大的排序std::sort(s.begin(), s.end()); // 将饼干的尺寸进行从小到大的排序int count = 0; // 记录得到满足的小孩的数量for(int i = 0, j = 0; i < g.size() && j < s.size();){if(s[j] >= g[i]){count++;i++;j++;}else{j++;}}return count;}};
3、摆动序列
思路1（贪心算法）
例如，[1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。其实满足条件的序列就是一个个锯齿形。
至于，子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
其实只要不记录就达到了删除的目的。但是有一些特殊情况需要处理。
例如序列[2,5]，它的峰值数量是2，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
所以可以针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即preDiff = 0，如图：
针对以上情形，result初始为1（默认最右面有一个峰值），此时curDiff > 0 && preDiff <= 0，那么result++（计算了左面的峰值），最后得到的result就是2（峰值个数为2即摆动序列长度为2）
贪心算法C++代码：
class Solution {public:int wiggleMaxLength(vector<int>& nums) {if(nums.size() <= 1) return nums.size();int preDiff = 0; // 记录前一对的差值int curDiff = 0; // 记录当前一对的差值int result = 1; // 初始化为，应对类似[2,5]这种情况for(int i = 0; i < nums.size(); i++){if(i >= 1){curDiff = nums[i] - nums[i - 1];}// 出现峰值if((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)){preDiff = curDiff;result++;}}return result;}};
- 时间复杂度O(n)
- 空间复杂度O(1)
思路2（动态规划，不懂啊！）
考虑用动态规划的思想来解决这个问题。
很容易可以发现，对于我们当前考虑的这个数，要么是作为山峰（即nums[i] > nums[i-1]），要么是作为山谷（即nums[i] < nums[i - 1]）。
- 设dp状态dp[i][0]，表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度
- 设dp状态dp[i][1]，表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度
则转移方程为：
- dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示将nums[i]接到前面某个山谷后面，作为山峰。
- dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示将nums[i]接到前面某个山峰后面，作为山谷。
初始状态：
由于一个数可以接到前面的某个数后面，也可以以自身为子序列的起点，所以初始状态为：dp[0][0] = dp[0][1] = 1。
C++代码如下：
class Solution {public:int dp[1000][2];int wiggleMaxLength(vector<int>& nums) {memset(dp, 0, sizeof dp);dp[0][0] = dp[0][1] = 1;for(int i = 1; i < nums.size(); i++){dp[i][0] = dp[i][1] = 1;for(int j = 0; j < i; j++){if(nums[j] > nums[i]){dp[i][1] = max(dp[i][1], dp[j][0] + 1);}}for(int j = 0; j < i; j++){if(nums[j] < nums[i]){dp[i][0] = max(dp[i][0], dp[j][1] + 1);}}}return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);}};
4、最大子序和
思路
暴力法
暴力解法在LC上是过不了的，只是多一种思路
class Solution {public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN; // 最终结果int curSum = 0; // 当前和for(int i = 0; i < nums.size(); i++){curSum = 0;for(int j = i; j < nums.size(); j++){curSum = curSum + nums[j];result = curSum > result ? curSum : result;}}return result;}};
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
贪心解法
- 贪心解法贪的是哪里呢？
- 局部最优：当前”连续和”为负数的时候应该立刻放弃，从下一个元素重新计算”连续和”，因为负数加上下一个元素”连续和”只会越来越小。
- 全局最优：选取最大连续和
- 当curSum取到当前连续和的最大值的时候，要及时记录下来
红色的起始位置就是贪心每次取count为正数的时候，开始一个区间的统计。
C++完整代码如下：
class Solution {public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN; // 保存最终结果int curSum = 0; // 记录当前和if(nums.size() == 0) return 0; // 题目没有说返回什么，所以我们返回一个 0 即可for(int i = 0; i < nums.size(); i++){curSum = curSum + nums[i];result = curSum > result ? curSum : result; // 取区间累计的最大值（相当于不断确定最大子序终止位置）if(curSum <= 0){ // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和curSum = 0;}}return result;}};
- 时间复杂度O(n)
- 空间复杂度O(1)
动态规划
本题还可以使用动态规划来做，但是效率不如贪心算法，当作是思维的拓展。后面在动态规划的章节中，卡哥会详细解析这道题目。
class Solution {public:int maxSubArray(vector<int>& nums) {if(nums.size() == 0) return 0;vector<int> dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和dp[0] = nums[0];int result = dp[0];for(int i = 1; i < nums.size(); i++){dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式if(dp[i] > result){result = dp[i]; // result保存dp[i]的最大值}}return result;}};
5、贪心周总结
本周小结！（贪心算法系列一）
周一
本周正式开始了贪心算法，在关于贪心算法，你该了解这些！(opens new window)中，我们介绍了什么是贪心以及贪心的套路。
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
有没有啥套路呢？
不好意思，贪心没套路，就刷题而言，如果感觉好像局部最优可以推出全局最优，然后想不到反例，那就试一试贪心吧！
而严格的数据证明一般有如下两种：
- 数学归纳法
- 反证法
数学就不在讲解范围内了，感兴趣的同学可以自己去查一查资料。
正式因为贪心算法有时候会感觉这是常识，本就应该这么做！ 所以大家经常看到网上有人说这是一道贪心题目，有人是这不是。
这里说一下我的依据：如果找到局部最优，然后推出整体最优，那么就是贪心，大家可以参考哈。
周二
在贪心算法：分发饼干(opens new window)中讲解了贪心算法的第一道题目。
这道题目很明显能看出来是用贪心，也是入门好题。
我在文中给出局部最优：大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优：喂饱尽可能多的小孩。
很多录友都是用小饼干优先先喂饱小胃口的。
后来我想一想，虽然结果是一样的，但是大家的这个思考方式更好一些。
因为用小饼干优先喂饱小胃口的 这样可以尽量保证最后省下来的是大饼干（虽然题目没有这个要求）！
所有还是小饼干优先先喂饱小胃口更好一些，也比较直观。
一些录友不清楚贪心算法：分发饼干(opens new window)中时间复杂度是怎么来的？
就是快排$O(n\log n)$，遍历$O(n)$，加一起就是还是$O(n\log n)$。
周三
接下来就要上一点难度了，要不然大家会误以为贪心算法就是常识判断一下就行了。
在贪心算法：摆动序列(opens new window)中，需要计算最长摇摆序列。
其实就是让序列有尽可能多的局部峰值。
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
在计算峰值的时候，还是有一些代码技巧的，例如序列两端的峰值如何处理。
这些技巧，其实还是要多看多用才会掌握。
周四
在贪心算法：最大子序和(opens new window)中，详细讲解了用贪心的方式来求最大子序列和，其实这道题目是一道动态规划的题目。
贪心的思路为局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。从而推出全局最优：选取最大“连续和”
代码很简单，但是思路却比较难。还需要反复琢磨。
针对贪心算法：最大子序和(opens new window)文章中给出的贪心代码如下；
class Solution {public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) {count += nums[i];if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）result = count;}if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和}return result;}};
不少同学都来问，如果数组全是负数这个代码就有问题了，如果数组里有int最小值这个代码就有问题了。
大家不要脑洞模拟哈，可以亲自构造一些测试数据试一试，就发现其实没有问题。
数组都为负数，result记录的就是最小的负数，如果数组里有int最小值，那么最终result就是int最小值。
总结
本周我们讲解了贪心算法的理论基础(opens new window)，了解了贪心本质：局部最优推出全局最优。
然后讲解了第一道题目分发饼干(opens new window)，还是比较基础的，可能会给大家一种贪心算法比较简单的错觉，因为贪心有时候接近于常识。
其实我还准备一些简单的贪心题目，甚至网上很多都质疑这些题目是不是贪心算法。这些题目我没有立刻发出来，因为真的会让大家感觉贪心过于简单，而忽略了贪心的本质：局部最优和全局最优两个关键点。
所以我在贪心系列难度会有所交替，难的题目在于拓展思路，简单的题目在于分析清楚其贪心的本质，后续我还会发一些简单的题目来做贪心的分析。
在摆动序列(opens new window)中大家就初步感受到贪心没那么简单了。
本周最后是最大子序和(opens new window)，这道题目要用贪心的方式做出来，就比较有难度，都知道负数加上正数之后会变小，但是这道题目依然会让很多人搞混淆，其关键在于：不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数。这块真的需要仔细体会！
6、买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
思路
野路子解法
我的思路全在代码里，野路子来着，甚至感觉都没有贪心算法的思想。不像卡哥是正规军解法！
class Solution {public:int maxProfit(vector<int>& prices) {if(prices.size() <= 1){return 0;}int pay = 0; // 票友收益bool have = false; // 判断是否持有一股for(int i = 0; i < prices.size(); i++){// 买入// 只有当前的股票价格小于第二天的股票价格的时候才会买入，这样子才会有收益，这就是贪心所贪的地方if(i < prices.size() - 1 && prices[i] < prices[i + 1]){if(have == false){pay = pay - prices[i];have = true;}}// 卖出// 只有当前股票值大于第二天的股票价格的时候，我们才会卖出；或者，到了最后一个位置，才把股票卖出if((i < prices.size() - 1 && prices[i] > prices[i + 1]) || (i == prices.size() - 1)){if(have == true){pay = pay + prices[i];have = false;}}}return pay;}};
- 时间复杂度O(n)
- 空间复杂度O(1)
贪心算法
这道题目可能我们只会想，选一个低的买入，在选个高的卖，在选一个低的买入…..循环反复。
如果想到其实最终利润是可以分解的，那么本题就很容易了！
如何分解呢？
假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
那么根据prices可以得到每天的利润序列：(prices[i] - prices[i - 1])…..(prices[1] - prices[0])。
如图：
一些同学陷入：第一天怎么就没有利润呢，第一天到底算不算的困惑中
。
第一天当然没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！
从图中可以发现，其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。
那么只收集正利润就是贪心所贪的地方！
局部最优：收集每天的正利润，全局最优：求得最大利润。
局部最优可以推出全局最优，找不出反例，试一试贪心！
对应C++代码如下：
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;}};
- 时间复杂度O(n)
- 空间复杂度O(1)
动态规划
动态规划将在下一个系列详细讲解，本题解先给出我的C++代码（带详细注释），感兴趣的同学可以自己先学习一下。
class Solution {public:int maxProfit(vector<int>& prices) {// dp[i][1]第i天持有的最多现金// dp[i][0]第i天持有股票后的最多现金int n = prices.size();vector<vector<int>> dp(n, vector<int>(2, 0));dp[0][0] -= prices[0]; // 持股票for (int i = 1; i < n; i++) {// 第i天持股票所剩最多现金 = max(第i-1天持股票所剩现金, 第i-1天持现金-买第i天的股票)dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);// 第i天持有最多现金 = max(第i-1天持有的最多现金，第i-1天持有股票的最多现金+第i天卖出股票)dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return max(dp[n - 1][0], dp[n - 1][1]);}};
- 时间复杂度O(n)
- 空间复杂度O(n)
7、跳跃游戏
思路
刚看到本题一开始可能想：当前位置元素如果是3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？
其实跳几步无所谓，关键在于可跳的覆盖范围！
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
这个范围内，别管是怎么跳的，反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
局部最优推出全局最优，找不出反例，试试贪心！
如图：
i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。
如果cover大于等于了终点下标，直接return true就可以了。
C++代码如下：
class Solution {public:bool canJump(vector<int>& nums) {int cover = 0; // 覆盖的范围if(nums.size() == 1) return true; // 如果只有一个元素，那就是能够跳到for(int i = 0; i <= cover; i++){ // i只能在cover的覆盖的范围内移动cover = max(nums[i] + i, cover); // 不断更新覆盖范围if(cover >= nums.size() - 1){ // 说明可以跳到最后一个下标了return true;}}return false;}};
注意：这道题的关键是：不用拘泥于每次究竟跳几步，而是看覆盖的范围，覆盖的范围一定是可以跳跃过来的，而我们不必知道究竟是如何跳的。
8、跳跃游戏 II
思路
本题相对于55.跳跃游戏(opens new window)还是难了不少。
但思路是相似的，还是要看最大覆盖范围。
本题要计算最小步数，那么就要想清楚什么时候步数才一定要加一呢？
贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。
思路虽然是这样，但在写代码的时候还不能真的就能跳多远跳远，那样就不知道下一步最远能跳到哪里了。
所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。
如图：
图中覆盖范围的意义在于，只要红色的区域，最多两步一定可以到！（不用管具体怎么跳，反正一定可以跳到）
方法一
从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时
- 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
- 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。
C++代码如下：
class Solution{public:int jump(vector<int>& nums){if(nums.size() == 1) return 0; // 如果size==1,说明起点就是终点int curDistance = 0; // 当前这一步的覆盖范围int nextDistance = 0; // 下一步的覆盖范围int steps = 0; // 记录走过的步数for(int i = 0; i < nums.size(); i++){nextDistance = max(nums[i] + i, nextDistance); // 更新nextDistanceif(curDistance < nums.size() - 1){if(i == curDistance){ // 如果当前的覆盖范围与下标i相等，说明需要接着向后走了steps++; // 步数累加1curDistance = nextDistance; // 更新curDistanceif(nextDistance >= nums.size() - 1) break;}}else break;}return steps;}};
方法二
依然是贪心，思路和方法一差不多，代码可以简洁一些。
针对于方法一的特殊情况，可以统一处理，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。
这一步是关键，因为如果当前这一步的最大覆盖范围刚好是数组最后一个下标，这个时候会多加一次1，这里需要看代码仔细体会
因为当移动下标指向nums.size - 2时：
- 如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置）
- 如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。
class Solution{public:int jump(vector<int>& nums){if(nums.size() == 1) return 0; // 如果size==1,说明起点就是终点int curDistance = 0; // 当前这一步的覆盖范围int nextDistance = 0; // 下一步的覆盖范围int steps = 0; // 记录走过的步数for(int i = 0; i < nums.size() - 1; i++){ // 注意这里是小于nums.size() - 1，这是关键所在nextDistance = max(nums[i] + i, nextDistance); // 更新nextDistanceif(i == curDistance){ // 遇到当前覆盖的最远距离下标curDistance = nextDistance; // 更新当前覆盖的最远距离下标steps++;}}return steps;}};
9、K次取反后最大化的数组和
1005. K次取反后最大化的数组和 - 力扣（LeetCode)
思路
本题唯一有点难度的地方在于，你能不能想到将数组进行排序，如果想到这一点，这道题算是解出来了。
贪心思想：
- 局部最优：如果是负数，让最小的负数取反；如果是非负数，让值最小的数取反
- 全局最优：整个数组的和达到最大。
所以可以由 局部最优 —> 全局最优；符合贪心思想。
我的解题步骤：
- 对数组从小到大排序
- 将数组中的负数各取反一次，同时k—
- 判断k是否大于0，如果大于0，则对数组中最小的值取反，直到k为0；如果k不大于0，可以直接到第四步。
- 计算结果
C++完整代码
class Solution {public:int largestSumAfterKNegations(vector<int>& nums, int k) {if(nums.size() == 1) return nums[0];sort(nums.begin(), nums.end()); // 对数组进行从小到大的排序for(int i = 0; i < nums.size() && k > 0; i++){if(nums[i] < 0){nums[i] = -nums[i];k--;}}// 此时如果 k > 0，那么我们可以保证数组nums已经全部都是正数了if(k > 0){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;}};
卡哥的解题步骤（其实是一样的）
- 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
- 第二步：从前向后遍历，遇到负数将其变为正数，同时K—
- 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
- 第四步：求和
C++完整代码
class Solution {static bool cmp(int a, int b) {return abs(a) > abs(b);}public:int largestSumAfterKNegations(vector<int>& A, int K) {sort(A.begin(), A.end(), cmp); // 第一步for (int i = 0; i < A.size(); i++) { // 第二步if (A[i] < 0 && K > 0) {A[i] *= -1;K--;}}if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步int result = 0;for (int a : A) result += a; // 第四步return result;}};
10、贪心周总结
本周小结！（贪心算法系列二）
周一
一说到股票问题，一般都会想到动态规划，其实有时候贪心更有效！
在贪心算法：买卖股票的最佳时机II(opens new window)中，讲到只能多次买卖一支股票，如何获取最大利润。
这道题目理解利润拆分是关键点！ 不要整块的去看，而是把整体利润拆为每天的利润，就很容易想到贪心了。
局部最优：只收集每天的正利润，全局最优：得到最大利润。
如果正利润连续上了，相当于连续持有股票，而本题并不需要计算具体的区间。
如图：
周二
在贪心算法：跳跃游戏(opens new window)中是给你一个数组看能否跳到终点。
本题贪心的关键是：不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
贪心算法局部最优解：移动下标每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点
如果覆盖范围覆盖到了终点，就表示一定可以跳过去。
如图：
周三
这道题目：贪心算法：跳跃游戏II(opens new window)可就有点难了。
本题解题关键在于：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点。
那么局部最优：求当前这步的最大覆盖，那么尽可能多走，到达覆盖范围的终点，只需要一步。整体最优：达到终点，步数最少。
如图：
注意：图中的移动下标是到当前这步覆盖的最远距离（下标2的位置），此时没有到终点，只能增加第二步来扩大覆盖范围。
在贪心算法：跳跃游戏II(opens new window)中我给出了两个版本的代码。
其实本质都是超过当前覆盖范围，步数就加一，但版本一需要考虑当前覆盖最远距离下标是不是数组终点的情况。
而版本二就比较统一的，超过范围，步数就加一，但在移动下标的范围了做了文章。
即如果覆盖最远距离下标是倒数第二点：直接加一就行，默认一定可以到终点。如图： 
如果覆盖最远距离下标不是倒数第二点，说明本次覆盖已经到终点了。如图： 
有的录友认为版本一好理解，有的录友认为版本二好理解，其实掌握一种就可以了，也不用非要比拼一下代码的简洁性，简洁程度都差不多了。
我个人倾向于版本一的写法，思路清晰一点，版本二会有点绕。
周四
这道题目：贪心算法：K次取反后最大化的数组和(opens new window)就比较简单了，哈哈，用简单题来讲一讲贪心的思想。
这里其实用了两次贪心！
第一次贪心：局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
处理之后，如果K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。
第二次贪心：局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。
贪心算法：K次取反后最大化的数组和(opens new window)中的代码，最后while处理K的时候，其实直接判断奇偶数就可以了，文中给出的方式太粗暴了，哈哈，Carl大意了。
例外一位录友留言给出一个很好的建议，因为文中是使用快排，仔细看题，题目中限定了数据范围是正负一百，所以可以使用桶排序，这样时间复杂度就可以优化为$O(n)$了。但可能代码要复杂一些了。
11、加油站
思路
暴力解法
暴力法在LC上是无法通过的，就是多一种解题思路而已。
class Solution {public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int index = -1; // 记录位置for(int i = 0; i < gas.size(); i++){int oil = 0; // 汽车的油量for(index = i; index < gas.size() + i; index++){ // gas.size()+i，是为了保证index在每一次循环都能走一整圈oil = oil + gas[index % gas.size()] - cost[index % gas.size()];// cout << "[" << i << "]->" << oil << endl; // 打日志if(oil < 0){break;}}if(oil >= 0){return index % gas.size(); // 如果有解，马上返回}}return -1;}};
- 时间复杂度O(n^2)
- 空间复杂度O(n)
贪心算法（方法一）
直接从全局进行贪心选择，情况如下：
- 情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
- 情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
- 情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。
C++代码如下：
/*情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。*/class Solution {public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int min = INT_MAX; // 从起点出发，油量最多缺多少for(int i = 0; i < gas.size(); i++){curSum += gas[i] - cost[i];if(curSum < min){min = curSum;}}if(curSum < 0) return -1; // 情况一if(min >= 0) return 0; // 情况二// 情况三for(int i = gas.size() - 1; i >= 0; i--){min += gas[i] - cost[i];if(min >= 0){return i;}}return -1;}};
- 时间复杂度O(n)
- 空间复杂度O(1)
其实我不认为这种方式是贪心算法，因为没有找出局部最优，而是直接从全局最优的角度上思考问题。
但这种解法又说不出是什么方法，这就是一个从全局角度选取最优解的模拟操作。
所以对于本解法是贪心，我持保留意见！
但不管怎么说，解法毕竟还是巧妙的，不用过于执着于其名字称呼。
贪心算法（方法二）
可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
如图： 
那么为什么一旦[i，j] 区间和为负数，起始位置就可以是j+1呢，j+1后面就不会出现更大的负数？
如果出现更大的负数，就是更新j，那么起始位置又变成新的j+1了。
而且j之前出现了多少负数，j后面就会出现多少正数，因为耗油总和是大于零的（前提我们已经确定了一定可以跑完全程）。
那么局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。
局部最优可以推出全局最优，找不出反例，试试贪心！
C++代码如下：
class Solution {public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int totalSum = 0; // 全局油量剩余int curSum = 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){ // 当前累加和一旦小于0，说明当前加油站不符合start = i + 1; // 验证后面的加油站是否符合curSum = 0; // currSum需要清零}}if(totalSum < 0) return -1;return start;}};
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
说这种解法为贪心算法，才是是有理有据的，因为全局最优解是根据局部最优推导出来的。
12、分发糖果
思路
这道题如果没有弄清题意的话，就会很容易陷入陷阱。题目说的是相邻两个孩子，评分更高的会获得比评分低的孩子更多的糖果数（其实就是多一个），这一点需要搞明白了！
这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
先确定右边评分大于左边的情况（也就是从前向后遍历）
- 此时局部最优：只要 右边 评分比 左边 大，右边的孩子就多一个糖果，
- 全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
再确定左边评分大于右边的情况（也就是从后先前遍历）
- 此时局部最优：只要 右边 评分比 左边 大，右边的孩子就多一个糖果，
- 全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。
注意点
除此之外，还需要注意的一个点就是，为什么确定左边评分大于右边的情况需要从后向前遍历？为什么不能从前向后遍历呢？
因为如果从前向后遍历，根据 ratings[i + 1] 来确定 ratings[i] 对应的糖果，那么每次都不能利用上前一次的比较结果了。
所以确定左孩子大于右孩子的情况一定要从后向前遍历！
除此之外，这道困难题就没有什么难的地方了。
C++代码如下：
class Solution {public:int candy(vector<int>& ratings) {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], candyVec[i + 1] + 1);}}int result = 0;for(int i = 0; i < candyVec.size(); i++){result += candyVec[i];}return result;}};
13、柠檬水找零
思路：
我的思路是从全局出发，毫无贪心算法的痕迹，但是代码似乎不高效。如果非要说有贪心的思想，那就是每次找零的时候，都首先把零钱最大的先找出，这就是贪心所在了。确保全局有足够的零钱。
- 时间复杂度O(n)，准确来说是3n
- 空间复杂度O(1)
看了卡哥的解题思路，哈哈哈原来是一样的。那这样的话这道题真的极其容易了。但是写法不同，可以参照一下卡哥的写法：class Solution {public:bool lemonadeChange(vector<int>& bills) {vector<int> array(3, 0); // 索引0、1、2分别代表5、10、20美元for(int i = 0; i < bills.size(); i++){if(bills[i] == 5){array[0]++;}else if(bills[i] == 10){array[0]--;array[1]++;}else if(bills[i] == 20){if(array[1] >= 1){array[0]--;array[1]--;array[2]++;}else{array[0] -= 3;array[2]++;}}// 每次找零都要判断零钱是否足够，否则直接返回falsefor(int i = 0; i < array.size(); i++){if(array[i] < 0){return false;}}}return true;}};
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;}};
14、根据身高重建队列
思路
本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后在按照另一个维度重新排列。
其实如果大家认真做了135. 分发糖果(opens new window)，就会发现和此题有点点的像。
在135. 分发糖果(opens new window)我就强调过一次，遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
如果两个维度一起考虑一定会顾此失彼。
对于本题相信大家困惑的点是先确定k还是先确定h呢，也就是究竟先按h排序呢，还先按照k排序呢？
如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。
那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！
那么只需要按照k为下标重新插入队列就可以了，为什么呢？
以图中{5,2} 为例：
按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
所以在按照身高从大到小排序后：
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性
局部最优可推出全局最优，找不出反例，那就试试贪心。
一些同学可能也会疑惑，你怎么知道局部最优就可以推出全局最优呢？ 有数学证明么？
在贪心系列开篇词关于贪心算法，你该了解这些！(opens new window)中，我已经讲过了这个问题了。
刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心，至于严格的数学证明，就不在讨论范围内了。
如果没有读过关于贪心算法，你该了解这些！(opens new window)的同学建议读一下，相信对贪心就有初步的了解了。
回归本题，整个插入过程如下：
排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
插入的过程：
- 插入[7,0]：[[7,0]]
- 插入[7,1]：[[7,0],[7,1]]
- 插入[6,1]：[[7,0],[6,1],[7,1]]
- 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
- 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
- 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
此时就按照题目的要求完成了重新排列。
C++代码如下
class Solution {public:// 先按照身高h排序，如果身高h相同，那么k小的排在前面static bool cmp(vector<int>& a, vector<int>& b){if(a[0] == b[0]){return a[1] < b[1];}return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {vector<vector<int>> que;sort(people.begin(), people.end(), cmp); // 自定义排序for(int i = 0; i < people.size(); i++){int position = people[i][1]; // 要插入的位置que.insert(que.begin() + position, people[i]); // 频繁的insert开销很大}return que;}};
- 时间复杂度：$O(n\log n + n^2)$
- 空间复杂度：$O(n)$
但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。
所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是$O(n^2)$了，甚至可能拷贝好几次，就不止$O(n^2)$了。（注意！卡哥这里的意思是insert操作已经在一个for循环里面了，所以才是n^2，单说insert操作的话，时间复杂度是O(n) ）！
改成链表之后，C++代码如下：
class Solution {public:// 先按照身高h从大到小排序，如果身高h相同，那么k小的排在前面static bool cmp(vector<int>& a, vector<int>& b){if(a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {std::list<vector<int>> que; // list的低层实现是双向链表sort(people.begin(), people.end(), cmp); // 自定义排序for(int i = 0; i < people.size(); i++){int position = people[i][1]; // 要插入的位置std::list<vector<int>>::iterator it = que.begin(); // 通过迭代器获取list的位置while(position--){it++; // 找到要插入的位置}que.insert(it, people[i]);}return vector<vector<int>>(que.begin(), que.end()); // 注意，题目要求的返回值类型是vector<vector<int>>}};
- 时间复杂度：$O(n\log n + n^2)$
- 空间复杂度：$O(n)$
总结
关于出现两个维度一起考虑的情况，我们已经做过两道题目了，另一道就是135. 分发糖果(opens new window)。
其技巧都是确定一边然后贪心另一边，两边一起考虑，就会顾此失彼。
这道题目可以说比135. 分发糖果(opens new window)难不少，其贪心的策略也是比较巧妙。
最后我给出了两个版本的代码，可以明显看是使用C++中的list（底层链表实现）比vector（数组）效率高得多。
对使用某一种语言容器的使用，特性的选择都会不同程度上影响效率。
所以很多人都说写算法题用什么语言都可以，主要体现在算法思维上，其实我是同意的但也不同意。
对于看别人题解的同学，题解用什么语言其实影响不大，只要题解把所使用语言特性优化的点讲出来，大家都可以看懂，并使用自己语言的时候注意一下。
对于写题解的同学，刷题用什么语言影响就非常大，如果自己语言没有学好而强调算法和编程语言没关系，其实是会误伤别人的。
这也是我为什么统一使用C++写题解的原因，其实用其他语言java、python、php、go啥的，我也能写，我的Github上也有用这些语言写的小项目，但写题解的话，我就不能保证把语言特性这块讲清楚，所以我始终坚持使用最熟悉的C++写题解。
而且我在写题解的时候涉及语言特性，一般都会后面加上括号说明一下。没办法，认真负责就是我，哈哈。
15、贪心周总结
看卡哥的，懒得cv了。
代码随想录 - 贪心算法 - 15. 贪心周总结
16、根据身高重建队列（vector原理讲解）
贪心算法：根据身高重建队列（续集）
在讲解贪心算法：根据身高重建队列(opens new window)中，我们提到了使用vector（C++中的动态数组）来进行insert操作是费时的。
但是在解释的过程中有不恰当的地方，所以来专门写一篇文章来详细说一说这个问题。
使用vector的代码如下：
// 版本一，使用vector（动态数组）class Solution {public:static bool cmp(const vector<int> a, const vector<int> b) {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;for (int i = 0; i < people.size(); i++) {int position = people[i][1];que.insert(que.begin() + position, people[i]);}return que;}};
耗时如下： 
其直观上来看数组的insert操作是$O(n)$的，整体代码的时间复杂度是$O(n^2)$。
这么一分析好像和版本二链表实现的时间复杂度是一样的啊，为什么提交之后效率会差距这么大呢？
// 版本二，使用list（链表）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];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort (people.begin(), people.end(), cmp);list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多for (int i = 0; i < people.size(); i++) {int position = people[i][1]; // 插入到下标为position的位置std::list<vector<int>>::iterator it = que.begin();while (position--) { // 寻找在插入位置it++;}que.insert(it, people[i]);}return vector<vector<int>>(que.begin(), que.end());}};
耗时如下：
大家都知道对于普通数组，一旦定义了大小就不能改变，例如int a[10];，这个数组a至多只能放10个元素，改不了的。
对于动态数组，就是可以不用关心初始时候的大小，可以随意往里放数据，那么耗时的原因就在于动态数组的底层实现。
动态数组为什么可以不受初始大小的限制，可以随意push_back数据呢？
首先vector的底层实现也是普通数组。
vector的大小有两个维度一个是size一个是capicity，size就是我们平时用来遍历vector时候用的，例如：
for (int i = 0; i < vec.size(); i++) {}
而capicity是vector底层数组（就是普通数组）的大小，capicity可不一定就是size。
当insert数据的时候，如果已经大于capicity，capicity会成倍扩容，但对外暴漏的size其实仅仅是+1。
那么既然vector底层实现是普通数组，怎么扩容的？
就是重新申请一个二倍于原数组大小的数组，然后把数据都拷贝过去，并释放原数组内存。（对，就是这么原始粗暴的方法！）
举一个例子，如图： 
原vector中的size和capicity相同都是3，初始化为1 2 3，此时要push_back一个元素4。
那么底层其实就要申请一个大小为6的普通数组，并且把原元素拷贝过去，释放原数组内存，注意图中底层数组的内存起始地址已经变了。
同时也注意此时capicity和size的变化，关键的地方我都标红了。
而在贪心算法：根据身高重建队列(opens new window)中，我们使用vector来做insert的操作，此时大家可会发现，虽然表面上复杂度是$O(n^2)$，但是其底层都不知道额外做了多少次全量拷贝了，所以算上vector的底层拷贝，整体时间复杂度可以认为是$O(n^2 + t × n)$级别的，t是底层拷贝的次数。
那么是不是可以直接确定好vector的大小，不让它在动态扩容了，例如在贪心算法：根据身高重建队列(opens new window)中已经给出了有people.size这么多的人，可以定义好一个固定大小的vector，这样我们就可以控制vector，不让它底层动态扩容。
这种方法需要自己模拟插入的操作，不仅没有直接调用insert接口那么方便，需要手动模拟插入操作，而且效率也不高！
手动模拟的过程其实不是很简单的，需要很多细节，我粗略写了一个版本，如下：
// 版本三// 使用vector，但不让它动态扩容class Solution {public:static bool cmp(const vector<int> a, const vector<int> b) {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(people.size(), vector<int>(2, -1));for (int i = 0; i < people.size(); i++) {int position = people[i][1];if (position == que.size() - 1) que[position] = people[i];else { // 将插入位置后面的元素整体向后移for (int j = que.size() - 2; j >= position; j--) que[j + 1] = que[j];que[position] = people[i];}}return que;}};
耗时如下：
这份代码就是不让vector动态扩容，全程我们自己模拟insert的操作，大家也可以直观的看出是一个$O(n^2)$的方法了。
但这份代码在leetcode上统计的耗时甚至比版本一的还高，我们都不让它动态扩容了，为什么耗时更高了呢？
一方面是leetcode的耗时统计本来就不太准，忽高忽低的，只能测个大概。
另一方面：可能是就算避免的vector的底层扩容，但这个固定大小的数组，每次向后移动元素赋值的次数比方法一中移动赋值的次数要多很多。
因为方法一中一开始数组是很小的，插入操作，向后移动元素次数比较少，即使有偶尔的扩容操作。而方法三每次都是按照最大数组规模向后移动元素的。
所以对于两种使用数组的方法一和方法三，也不好确定谁优，但一定都没有使用方法二链表的效率高！
一波分析之后，对于贪心算法：根据身高重建队列(opens new window)，大家就安心使用链表吧！别折腾了，哈哈，相当于我替大家折腾了一下。
17、用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
思路
- 先对数组进行排序，方便后续的比较
- 将开始直径Xstart 按照从小到大进行排序,如果Xstart一样，那么按照Xend从小到大排序
- 初始化箭的数量为1；
- 如果两个气球没有相交，那么加一支箭；如果相交那么不加
- 更新重叠气球的最小右边界，并在下一次循环重复利用；如果下次气球的起始直径与上次重叠气球的最小右边界没有交集，那么加一支箭，否则不加。
C++完整代码如下：
class Solution {public:// 将开始直径Xstart 按照从小到大进行排序,如果Xstart一样，那么按照Xend从小到大排序static bool cmp(vector<int>& a, vector<int>& b){if(a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}int findMinArrowShots(vector<vector<int>>& points) {if(points.size() == 0) return 0;sort(points.begin(), points.end(), cmp); // 自定义排序int arrows = 1; // points 不为空至少需要一支箭for(int i = 1; i < points.size(); i++){if(points[i][0] > points[i - 1][1]){ // 气球i和气球i-1不挨着，注意这里不是>=arrows++; // 需要一支箭}else{points[i][1] = min(points[i][1], points[i - 1][1]); // 更新重叠气球的最小右边界}}return arrows;}};
- 时间复杂度：$O(n\log n)$，因为有一个快排
- 空间复杂度：$O(1)$
18、无重复区间
思路
这道题的思路和上面的452. 用最少数量的箭引爆气球 - 力扣（LeetCode）基本一致。只不过这里的重叠的意思是需要相交。同样的步骤：
- 对数组进行自定义排序，按照左区间从小到大排序，如果左区间相等，那么按照右区间从小到大排序
- 判断是否相交，如果相交，需要移除的数量+1
- 更新重叠区间的最小右边界【这是关键】
C++完整代码如下：
class Solution {private:// 按左区间从小到大排序，如果左区间相等，那么按照右区间从小到大进行排序static bool cmp(vector<int>& a, vector<int>& b){if(a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.size() == 1) return 0;int result = 0;std::sort(intervals.begin(), intervals.end()); // 对数组intervals进行排序for(int i = 1; i < intervals.size(); i++){if(intervals[i - 1][1] > intervals[i][0]){result++; // 如果相交了，那么需要移除的数量+1intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠区间的最小右边界}}return result;}};
- 时间复杂度：$O(n\log n)$ ，有一个快排
- 空间复杂度：$O(1)$
我的思路和卡哥的不太一样，但都能接出来，时间复杂度和代码复杂度也差不多。
19、划分字母区间
思路
一想到分割字符串就想到了回溯，但本题其实不用回溯去暴力搜索。
题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？
如果没有接触过这种题目的话，还挺有难度的。
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
如图：
C++代码如下：
class Solution {public:vector<int> partitionLabels(string s) {int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置for(int i = 0; i < s.size(); i++){hash[s[i] - 'a'] = i; // 统计每一个字符最后出现的位置}int left = 0;int right = 0;vector<int> result;for(int i = 0; i < s.size(); i++){right = max(right, hash[s[i] - 'a']); // 找到字符出现的最远边界if(i == right){ // 如果字符出现最远的位置的下标与i相等了，说明当前是最短的一个满足题意的片段result.push_back(right - left + 1);left = i + 1;}}return result;}};
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$，使用的hash数组是固定大小
卡哥说他没有感受到这道题的贪心思想。但是我觉得还是有的。
- 局部最优：找到一个字符出现的最远的位置与当前的 i 相等了，说明当前是一个最短的满足题意的片段，贪的就是这个短。
- 全局最优：局部字符串最短，可以得到全局尽可能多的片段。
20、合并区间
思路
大家应该都感觉到了，此题一定要排序，那么按照左边界排序，还是右边界排序呢？
都可以！
那么我按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
局部最优可以推出全局最优，找不出反例，试试贪心。
那有同学问了，本来不就应该合并最大右边界么，这和贪心有啥关系？
有时候贪心就是常识！哈哈
按照左边界从小到大排序之后，如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]左边界 < intervals[i - 1]右边界，则一定有重复，因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。
即：intervals[i]的左边界在intervals[i - 1]左边界和右边界的范围内，那么一定有重复！
这么说有点抽象，看图：（注意图中区间都是按照左边界排序之后了）
知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？
其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
C++代码如下：
class Solution {private:// 按照左区间从小到大排序，如果左区间相等，那么按照右区间从小到大排序static bool cmp(vector<int>& a, vector<int>& b){if(a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if(intervals.size() == 1) return intervals;vector<vector<int>> result;bool flag = false; // 判断最后一个区间有没有被合并,被合并为true，否则为falseint length = intervals.size();sort(intervals.begin(), intervals.end(), cmp);for(int i = 1; i < intervals.size(); i++){int start = intervals[i - 1][0]; // 初始化i-1区间的左边界int end = intervals[i - 1][1]; // 初始化i-1区间的右边界while(i < length && intervals[i][0] <= end){ // 合并区间end = max(end, intervals[i][1]); // 不断更新右区间if(i == length - 1) flag = true; // 最后一个区间也合并了i++; // 继续合并下一个区间}// start和end是表示intervals[i - 1]的左边界右边界，所以最优intervals[i]区间是否合并了要标记一下result.push_back({start, end});}// 如果最后一个区间没有合并，将其加入resultif(flag == false) result.push_back( {intervals[intervals.size() - 1][0], intervals[intervals.size() - 1][1]} );return result;}};
当然以上代码有冗余一些，可以优化一下，如下：（思路是一样的）
class Solution {public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result;// 排序的参数使用了lamda表达式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});result.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 合并区间result.back()[1] = max(result.back()[1], intervals[i][1]);} else {result.push_back(intervals[i]);}}return result;}};
- 时间复杂度：$O(n\log n)$ ，有一个快排
- 空间复杂度：$O(1)$，我没有算result数组（返回值所需容器占的空间）
21、贪心周总结
22、单调递增的数字
暴力解法【by Jungle】
class Solution {public:int monotoneIncreasingDigits(int n) {int left = 0; // 整数除以10再模10得到的这个整数倒数第二个数int right = 0; // 整数模10得到的这个整数最右边的数int flag = 0; // 判断这个整数是否满足条件for(int i = n; i >= 0; i--){flag = 1;int temp = i;while(temp > 0){right = temp % 10;left = temp / 10 % 10;if(right < left){flag = 0;break;}temp = temp / 10;}if(flag == 1){return i;}}return 0;}};
贪心算法
题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]—，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
这一点如果想清楚了，这道题就好办了。
局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]—，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
全局最优：得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。
此时是从前向后遍历还是从后向前遍历呢？
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
所以从前后向遍历会改变已经遍历过的结果！
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。
不能这么写
class Solution {public:int monotoneIncreasingDigits(int n) {string strNum = std::to_string(n);int flag = strNum.size();for(int i = strNum.size() - 1; i > 0; i--){if(strNum[i - 1] > strNum[i]){strNum[i] = '9';strNum[i - 1]--;}}return stoi(strNum);}};
原因如下：
正确写法
class Solution {public:int monotoneIncreasingDigits(int n) {string strNum = std::to_string(n);// flag用来标记赋值9从哪里开始// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行int flag = strNum.size();for(int i = strNum.size() - 1; i > 0; i--){if(strNum[i - 1] > strNum[i]){flag = i;strNum[i - 1]--;}}for(int i = flag; i < strNum.size(); i++){strNum[i] = '9';}return stoi(strNum);}};
- 时间复杂度：$O(n)$，n 为数字长度
- 空间复杂度：$O(n)$，需要一个字符串，转化为字符串操作更方便
23、买卖股票的最佳实际含手续费
714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
思路
本题相对于贪心算法：122.买卖股票的最佳时机II(opens new window)，多添加了一个条件就是手续费。
贪心算法
在贪心算法：122.买卖股票的最佳时机II(opens new window)中使用贪心策略不用关心具体什么时候买卖，只要收集每天的正利润，最后稳稳的就是最大利润了。
而本题有了手续费，就要关系什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以手续费的情况。
如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。
此时无非就是要找到两个点，买入日期，和卖出日期。
- 买入日期：其实很好想，遇到更低点就记录一下。
- 卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。
所以我们在做收获利润操作的时候其实有三种情况：
- 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
- 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
- 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
class Solution {public:int maxProfit(vector<int>& prices, int fee) {int result = 0;int minPrice = prices[0]; // 记录最低价格for(int i = 1; i < prices.size(); i++){// 情况二，相当于买入if(prices[i] < minPrice) minPrice = prices[i];// 情况三，保持原状态（因为此时买则不便宜，卖则亏损）if(prices[i] >= minPrice && prices[i] <= minPrice + fee){continue;}// 计算利润，可能有多次计算利润，最后一次计算利润才是最终的收益if(prices[i] > minPrice + fee){result += prices[i] - minPrice - fee;// 情况一，这一步很关键; 为什么 minPrice = prices[i] - fee 呢？// 因为当前的收益可能不是最终的收益，如何判断后面还有收益呢？那就需要用到上次的prices[i - 1]了，// 其实应该是 if(prices[i] > prices[i - 1])，但是为了兼容还没有收益的情况，所以用 prices[i] > minPrice + fee// 所以 min 就需要 = prices[i] - fee 了// 所以说这一步很关键，也有点难minPrice = prices[i] - fee;}}return result;}};
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
动态规划
24、监控二叉树（困难）
思路
这道题目首先要想，如何放置，才能让摄像头最小的呢？
从题目中示例，其实可以得到启发，我们发现题目示例中的摄像头都没有放在叶子节点上！
这是很重要的一个线索，摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。
所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
那么有同学可能问了，为什么不从头结点开始看起呢，为啥要从叶子节点看呢？
因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！
局部最优推出全局最优，找不出反例，那么就按照贪心来！
此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。
此时这道题目还有两个难点：
- 二叉树的遍历
- 如何隔两个节点放一个摄像头
确定遍历顺序
在二叉树中如何从低向上推导呢？
可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。
后序遍历代码如下：
int traversal(TreeNode* cur) {// 空节点，该节点有覆盖if (终止条件) return ;int left = traversal(cur->left); // 左int right = traversal(cur->right); // 右逻辑处理 // 中return ;}
注意在以上代码中我们取了左孩子的返回值，右孩子的返回值，即left 和 right， 以后推导中间节点的状态
如何隔两个节点放一个摄像头
此时需要状态转移的公式，大家不要和动态的状态转移公式混到一起，本题状态转移没有择优的过程，就是单纯的状态转移！
来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：
有如下三种：
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖
我们分别有三个数字来表示：
- 0：该节点无覆盖
- 1：本节点有摄像头
- 2：本节点有覆盖
大家应该找不出第四个节点的状态了。
一些同学可能会想有没有第四种状态：本节点无摄像头，其实无摄像头就是 无覆盖 或者 有覆盖的状态，所以一共还是三个状态。
因为在遍历树的过程中，就会遇到空节点，那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？
回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。
那么空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。
所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了
接下来就是递推关系。
那么递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖），原因上面已经解释过了。
代码如下：
// 空节点，该节点有覆盖if (cur == NULL) return 2;
递归的函数，以及终止条件已经确定了，再来看单层逻辑处理。
主要有如下四类情况：
- 情况1：左右节点都有覆盖
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
如图：
代码如下：
// 左右节点都有覆盖if (left == 2 && right == 2) return 0;
- 情况2：左右节点至少有一个无覆盖的情况
如果是以下情况，则中间节点（父节点）应该放摄像头：
left == 0 && right == 0 左右节点无覆盖 left == 1 && right == 0 左节点有摄像头，右节点无覆盖 left == 0 && right == 1 左节点有无覆盖，右节点摄像头 left == 0 && right == 2 左节点无覆盖，右节点覆盖 left == 2 && right == 0 左节点覆盖，右节点无覆盖
这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。
此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。
代码如下：
if (left == 0 || right == 0) {result++;return 1;}
- 情况3：左右节点至少有一个有摄像头
如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）
left == 1 && right == 2 左节点有摄像头，右节点有覆盖 left == 2 && right == 1 左节点有覆盖，右节点有摄像头 left == 1 && right == 1 左右节点都有摄像头
代码如下：
if (left == 1 || right == 1) return 2;
从这个代码中，可以看出，如果left == 1, right == 0 怎么办？其实这种条件在情况2中已经判断过了，如图：
这种情况也是大多数同学容易迷惑的情况。
- 情况4：头结点没有覆盖
以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：
所以递归结束之后，还要判断根节点，如果没有覆盖，result++，代码如下：
int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) { // root 无覆盖result++;}return result;}
以上四种情况我们分析完了，代码也差不多了，整体代码如下：
（以下我的代码注释很详细，为了把情况说清楚，特别把每种情况列出来。）
C++代码如下：
/*** 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* root){if(root == nullptr) return 2; // 叶子节点默认被覆盖了int left = traversal(root->left);int right = traversal(root->right);// 情况1// 如果左右节点都被覆盖了，说明父节点没有被覆盖if(left == 2 && right == 2) return 0;// 情况2// left == 0 && right == 0 左右节点没有被覆盖// left == 1 && right == 0 左节点有摄像头，右节点没有被覆盖// left == 0 && right == 1 左节点没有被覆盖，右节点有摄像头// left == 2 && right == 0 左节点被覆盖，右节点没有被覆盖// left == 0 && right == 2 左节点没有被覆盖，右节点被覆盖if(left == 0 || right == 0){result++;return 1; // 父节点装上了摄像头}// 情况3// left == 1 && right == 1 左右节点都有摄像头// left == 1 && right == 2 左节点有摄像头，右节点被覆盖// left == 2 && right == 1 左节点被覆盖，右节点有摄像头// 其他情况前面的代码均已覆盖if(left == 1 || right == 1){return 2;}// 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解// 这个 return -1 逻辑不会走到这里。return -1;}int minCameraCover(TreeNode* root) {// 情况4if(traversal(root) == 0){ // root无覆盖的情况result++;}return result;}};
在以上代码的基础上，再进行精简，代码如下：
// 版本二class Solution {private:int result;int traversal(TreeNode* cur) {if (cur == NULL) return 2;int left = traversal(cur->left); // 左int right = traversal(cur->right); // 右if (left == 2 && right == 2) return 0;else if (left == 0 || right == 0) {result++;return 1;} else return 2;}public:int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) { // root 无覆盖result++;}return result;}};
大家可能会惊讶，居然可以这么简短，其实就是在版本一的基础上，使用else把一些情况直接覆盖掉了。
在网上关于这道题解可以搜到很多这种神级别的代码，但都没讲不清楚，如果直接看代码的话，指定越看越晕，所以建议大家对着版本一的代码一步一步来哈，版本二中看不中用！。
总结
本题的难点首先是要想到贪心的思路，然后就是遍历和状态推导。
在二叉树上进行状态推导，其实难度就上了一个台阶了，需要对二叉树的操作非常娴熟。
这道题目是名副其实的hard，大家感受感受，哈哈。
25、贪心算法总结篇
若有收获，就点个赞吧
0 人点赞
