代码随想录算法训练营第二十五天｜ 455.分发饼干、376. 摆动序列、53. 最大子序和

455.分发饼干

目标：

• g[i]：第i个孩子的胃口值（至少要这么大的饼干才满足）
• s[j]：第j块饼干的尺寸
  每个孩子最多一块饼干、每块饼干最多给一个孩子。
  问最多能满足多少孩子。

核心思路：贪心 + 排序 + 双指针

策略：用最小的饼干去满足胃口最小的孩子，能满足就给，不满足就换更大的饼干。

步骤：

1. g、s都排序
2. 两个指针：
   • i指向当前孩子（从小胃口开始）
   • j指向当前饼干（从小尺寸开始）
3. 如果s[j] >= g[i]：满足一个孩子，i += 1, j += 1
4. 否则：饼干太小，只能换更大的饼干，j += 1

代码

classSolution:deffindContentChildren(self,g:List[int],s:List[int])->int:# 让“最小胃口”优先配“最小能满足它的饼干”g.sort()s.sort()i=0# 孩子指针：当前要满足的孩子j=0# 饼干指针：当前可用的最小饼干count=0whilei<len(g)andj<len(s):# 当前饼干能满足当前孩子：成功分配ifg[i]<=s[j]:i+=1j+=1count+=1else:# 饼干太小，无法满足任何“更大胃口”的孩子# 只能丢掉这块饼干，换下一块更大的j+=1returncount

只要“孩子还没分完”并且“饼干还没用完”，分配就有意义。少一个都不行。
所以必须是：

whilei<len(g)andj<len(s):

376. 摆动序列

目标：
给你一个整数数组nums，找一个最长子序列，满足：

• 相邻差值正负交替

  nums=[1,7,4,9,2,5]diff=[+6,-3,+5,-7,+3]✅ 全程交替 答案=6

• 子序列不要求连续（可以跳着选）

👉 返回这个最长长度。

核心思路（贪心）

我们只关心“方向有没有变”，不关心数值具体多大。
只要方向变了，就一定能多摆一下。

我们同时维护两种“结尾状态”：

我们在贪：尽可能多地制造“方向切换”

只在方向发生改变的时候更新：

如果今天比昨天高： 说明出现“上升” 那我可以接在“下降”后面 → up = down + 1 如果今天比昨天低： 说明出现“下降” 那我可以接在“上升”后面 → down = up + 1

⚠️ 如果相等：

• 没有方向
• 对摆动没帮助
• 直接忽略

代码

classSolution:defwiggleMaxLength(self,nums:List[int])->int:# 边界情况：0 或 1 个数iflen(nums)<2:returnlen(nums)# up: 以“上升”结尾的最长摆动子序列长度# down: 以“下降”结尾的最长摆动子序列长度up=down=1foriinrange(1,len(nums)):ifnums[i]>nums[i-1]:# 当前是上升 → 可以接在“下降”后面up=down+1elifnums[i]<nums[i-1]:# 当前是下降 → 可以接在“上升”后面down=up+1else:# 相等则忽略（不会形成摆动）continuereturnmax(up,down)

53. 最大子序和

目标：
给你一个整数数组nums，找一个连续子数组（必须连续），使它的和最大，返回这个最大和。

nums=[-2,1,-3,4,-1,2,1,-5,4]最大子数组=[4,-1,2,1]答案=6

核心思路（Kadane）

要么把当前数接在“之前的好子数组”后面，要么从当前数重新开始。

一段连续子数组，只要“前面已经亏钱了”，后面不管赚多少，都不该带着它

为什么这是“贪心且不会后悔”？

因为有一个铁律：

任何负的前缀，都只会拖后腿，
不可能让后面的子数组变得更大。

所以：

• 丢掉负前缀 = 永远正确
• 不存在“先忍着亏，后面赚更多”的情况

现在数组里的每个数可以想成：

• 正数：赚钱
• 负数：亏钱

你要找一段连续时间里赚得最多。

关键问题只有一个
当前这一刻，我是继续之前的这段“投资”，还是重新开一个新的？

情况 1：之前是正的

之前赚了+5现在来一个+3

👉 当然要接上
总收益 = 8（更大）

情况 2：之前是负的

之前亏了-5现在来一个+3

👉 立刻丢掉之前的
只要 +3 比 -2 好

所以我们维护两个量就够了：

• cur_sum：以当前位置结尾的最大子数组和
• max_sum：目前为止见过的全局最大子数组和

代码

classSolution:defmaxSubArray(self,nums:List[int])->int:# cur_sum：以当前元素结尾的最大子数组和cur_sum=nums[0]# max_sum：目前为止见过的最大子数组和max_sum=nums[0]foriinrange(1,len(nums)):# 核心贪心：要不要之前那段？# 如果之前是负的，直接丢掉，从 nums[i] 重新开始cur_sum=max(nums[i],cur_sum+nums[i])# 更新全局最大值max_sum=max(max_sum,cur_sum)returnmax_sum