java算法第31天 | 贪心算法 part01 ● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

本文主要是介绍java算法第31天 | 贪心算法 part01 ● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

理论基础

贪心算法没有固定的套路，贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

贪心算法一般分为如下四步：

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
这个四步其实过于理论化了，我们平时在做贪心类的题目很难去按照这四步去思考，真是有点“鸡肋”。

做题的时候，只要想清楚局部最优是什么，如果推导出全局最优，其实就够了。

455.分发饼干

在这里插入图片描述

这道题有点类似双指针，每一尽可能使用当前最大的饼干去满足胃口最大地小朋友。
注意： 要先对两个数组排序。

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int index=s.length-1;int res=0;for(int i=g.length-1;i>=0;i--){//使用循环遍历孩子的胃口（从大到小）if(index>=0 && s[index]>=g[i]){index--; res++;} }return res;}
}

时间复杂度：O(nlogn)
空间复杂度：O(1)

376. 摆动序列

在这里插入图片描述

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）。
在这里插入图片描述
要注意的是重复元素的处理：pre只记录前一个非平的坡度。
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length<=1) return 1;
int pre=0;//记录上一个升或降的记录
int cur=0;//当前的记录
int count=1;
for(int i=1;i<nums.length;i++){
cur=nums[i]-nums[i-1];
if(pre>=0 && cur<0){
pre=cur;
count++;
}else if(pre<=0 && cur>0){
pre=cur;
count++;
}
}
return count;

}
时间复杂度：O(n)
空间复杂度：O(1)

53. 最大子序和

在这里插入图片描述

这道题的贪心体现在只要当前子数组的前缀和是负数，则直接舍弃，继续从下一个元素开始遍历。一个数res负责记录最大和，另一个负责记录当前前缀和。

class Solution {public int maxSubArray(int[] nums) {int res=Integer.MIN_VALUE;int count=0;for(int i=0;i<nums.length;i++){count+=nums[i];if(count>res) res=count;//存储当前最大子数组和if(count<0) count=0;//如果当前前缀和为负数，则清空count，从下一个开始}return res;}
}