算法D31 | 贪心算法1 | 455.分发饼干 376. 摆动序列 53. 最大子序和

贪心算法其实就是没有什么规律可言，所以大家了解贪心算法 就了解它没有规律的本质就够了。 

不用花心思去研究其规律， 没有思路就立刻看题解。

基本贪心的题目 有两个极端，要不就是特简单，要不就是死活想不出来。  

学完贪心之后再去看动态规划，就会了解贪心和动规的区别。

理论基础 

代码随想录

455.分发饼干  

代码随想录

两个数组先排序，倒着看最大的cookie能满足的孩子，向前计数。

Python:

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort()i = len(g)-1j = len(s)-1result = 0while j>=0 and i>=0:if s[j]>=g[i]:result += 1j -= 1i -= 1return result

C++:

C++版本用i--实现也算简洁。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int result=0;int i = g.size()-1;int j = s.size()-1;for (int i=g.size()-1; i>=0; i--) {if (j>=0 && s[j]>=g[i]) {result++;j--;}}return result;}
};

376. 摆动序列  

代码随想录

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

主要难点：要考虑平坡的情况。

Python:

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:n = len(nums)if n<=1: return nprev_diff = nums[1] - nums[0]n_diff = int(prev_diff!=0)for i in range(2, n):cur_diff = nums[i] - nums[i-1]if cur_diff * prev_diff < 0 or (prev_diff==0 and cur_diff!=0):n_diff += 1prev_diff = cur_diff return n_diff + 1

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;for (int i=0; i<nums.size()-1; i++) {curDiff = nums[i+1] - nums[i];if ((preDiff<=0 && curDiff>0) || (preDiff>=0 && curDiff<0)) {result++;preDiff = curDiff;}}return result;}
};

53. 最大子序和  

代码随想录

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。

这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

Python贪心:

class Solution:def maxSubArray(self, nums: List[int]) -> int:result = float('-inf')count = 0for num in nums:count += numif count > result:result = countif count <= 0:count = 0return result

Python动态规划：

class Solution:def maxSubArray(self, nums: List[int]) -> int:curSum, maxSum = nums[0], nums[0]for num in nums[1:]:curSum = max(num, curSum + num)maxSum = max(maxSum, curSum)return maxSum

C++贪心:

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; }
};

C++动态规划：

class Solution {
public:int maxSubArray(vector<int>& nums) {int curSum = nums[0];int maxSum = nums[0];for (int i=1; i<nums.size(); i++) {curSum = max(nums[i], curSum+nums[i]);maxSum = max(maxSum, curSum);}return maxSum;}
};