leetcode刷题day27|贪心算法Part01（455.分发饼干、376. 摆动序列、53. 最大子序和）

ops/2024/10/22 13:36:10/

前言：贪心的本质选择每一阶段的局部最优，从而达到全局最优。

455.分发饼干

思路：局部最优-大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个；全局最优：喂饱尽可能多的小孩。可以尝试使用贪心策略，先将饼干数组和小孩数组排序，然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。具体实现使用两个指针分别指向两个数组，最大的饼干能满足胃口最大的小孩，小孩数量加一，两个指针同时前移，如果最大的饼干不能满足，则小孩指针前移，继续判断。

代码如下：

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int sNum=s.length-1;int child=0;for(int i=g.length-1;i>=0;i--){if(sNum>=0 && g[i]<=s[sNum]){child++;sNum--;}}return child;}
}

注意：如果是想先喂饱大胃口的小孩，for循环只能是胃口，用下标控制饼干，这样才能满足条件时才移动饼干。

376. 摆动序列

思路：
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
实际操作可以不做删除操作，题目要求最长摆动子序列的长度，只需要统计数组的峰值数量即可。

考虑三种特殊情况：
情况一：上下坡中有平坡：这个时候需要考虑保留平坡左端点还是右端点，如果保留左端点即允许prediff==0。
情况二：数组首尾两端：只有两个元素时，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）
情况三：单调坡中有平坡：设置只有在峰值处将curDiff 赋值给preDiff。

代码如下：

class Solution {public int wiggleMaxLength(int[] nums) {int result=1;int preDiff=0;int curDiff=0;for(int i=1;i<nums.length;i++){curDiff=nums[i]-nums[i-1];if((preDiff<=0 && curDiff>0 )||(preDiff>=0 && curDiff<0)){result++;preDiff=curDiff;}}return result;}
}

53. 最大子序和

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

代码如下：

class Solution {public int maxSubArray(int[] nums) {int result=Integer.MIN_VALUE;int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];result=Math.max(result,sum);if(sum<=0){sum=0;}}return result;}
}