mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
116 lines
5.7 KiB
Markdown
116 lines
5.7 KiB
Markdown
|
||
# 本周小结！（贪心算法系列一）
|
||
|
||
## 周一
|
||
|
||
本周正式开始了贪心算法，在[关于贪心算法，你该了解这些！](https://programmercarl.com/贪心算法理论基础.html)中，我们介绍了什么是贪心以及贪心的套路。
|
||
|
||
**贪心的本质是选择每一阶段的局部最优，从而达到全局最优。**
|
||
|
||
有没有啥套路呢？
|
||
|
||
**不好意思，贪心没套路，就刷题而言，如果感觉好像局部最优可以推出全局最优，然后想不到反例，那就试一试贪心吧！**
|
||
|
||
而严格的数据证明一般有如下两种：
|
||
|
||
* 数学归纳法
|
||
* 反证法
|
||
|
||
数学就不在讲解范围内了，感兴趣的同学可以自己去查一查资料。
|
||
|
||
正是因为贪心算法有时候会感觉这是常识，本就应该这么做！ 所以大家经常看到网上有人说这是一道贪心题目，有人说这不是。
|
||
|
||
这里说一下我的依据：**如果找到局部最优，然后推出整体最优，那么就是贪心**，大家可以参考哈。
|
||
|
||
## 周二
|
||
|
||
|
||
在[贪心算法：分发饼干](https://programmercarl.com/0455.分发饼干.html)中讲解了贪心算法的第一道题目。
|
||
|
||
这道题目很明显能看出来是用贪心，也是入门好题。
|
||
|
||
我在文中给出**局部最优：大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优：喂饱尽可能多的小孩**。
|
||
|
||
很多录友都是用小饼干优先先喂饱小胃口的。
|
||
|
||
后来我想一想，虽然结果是一样的，但是大家的这个思考方式更好一些。
|
||
|
||
**因为用小饼干优先喂饱小胃口的 这样可以尽量保证最后省下来的是大饼干（虽然题目没有这个要求）！**
|
||
|
||
所以还是小饼干优先先喂饱小胃口更好一些，也比较直观。
|
||
|
||
一些录友不清楚[贪心算法：分发饼干](https://programmercarl.com/0455.分发饼干.html)中时间复杂度是怎么来的？
|
||
|
||
就是快排O(nlog n)，遍历O(n)，加一起就是还是O(nlogn)。
|
||
|
||
## 周三
|
||
|
||
接下来就要上一点难度了，要不然大家会误以为贪心算法就是常识判断一下就行了。
|
||
|
||
在[贪心算法：摆动序列](https://programmercarl.com/0376.摆动序列.html)中，需要计算最长摇摆序列。
|
||
|
||
其实就是让序列有尽可能多的局部峰值。
|
||
|
||
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
|
||
|
||
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
|
||
|
||
在计算峰值的时候，还是有一些代码技巧的，例如序列两端的峰值如何处理。
|
||
|
||
这些技巧，其实还是要多看多用才会掌握。
|
||
|
||
|
||
## 周四
|
||
|
||
在[贪心算法：最大子序和](https://programmercarl.com/0053.最大子序和.html)中，详细讲解了用贪心的方式来求最大子序列和，其实这道题目是一道动态规划的题目。
|
||
|
||
**贪心的思路为局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。从而推出全局最优：选取最大“连续和”**
|
||
|
||
代码很简单，但是思路却比较难。还需要反复琢磨。
|
||
|
||
针对[贪心算法：最大子序和](https://programmercarl.com/0053.最大子序和.html)文章中给出的贪心代码如下；
|
||
```cpp
|
||
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最小值。
|
||
|
||
|
||
## 总结
|
||
|
||
本周我们讲解了[贪心算法的理论基础](https://programmercarl.com/贪心算法理论基础.html)，了解了贪心本质：局部最优推出全局最优。
|
||
|
||
然后讲解了第一道题目[分发饼干](https://programmercarl.com/0455.分发饼干.html)，还是比较基础的，可能会给大家一种贪心算法比较简单的错觉，因为贪心有时候接近于常识。
|
||
|
||
其实我还准备一些简单的贪心题目，甚至网上很多都质疑这些题目是不是贪心算法。这些题目我没有立刻发出来，因为真的会让大家感觉贪心过于简单，而忽略了贪心的本质：局部最优和全局最优两个关键点。
|
||
|
||
**所以我在贪心系列难度会有所交替，难的题目在于拓展思路，简单的题目在于分析清楚其贪心的本质，后续我还会发一些简单的题目来做贪心的分析。**
|
||
|
||
在[摆动序列](https://programmercarl.com/0376.摆动序列.html)中大家就初步感受到贪心没那么简单了。
|
||
|
||
本周最后是[最大子序和](https://programmercarl.com/0053.最大子序和.html)，这道题目要用贪心的方式做出来，就比较有难度，都知道负数加上正数之后会变小，但是这道题目依然会让很多人搞混淆，其关键在于：**不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数**。这块真的需要仔细体会！
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<div align="center"><img src='https://file1.kamacoder.com/i/algo/01二维码.jpg' width=450> </img></div>
|