455.分发饼干
目标：
g[i]：第i个孩子的胃口值（至少要这么大的饼干才满足）s[j]：第j块饼干的尺寸
每个孩子最多一块饼干、每块饼干最多给一个孩子。
问最多能满足多少孩子。
核心思路：贪心 + 排序 + 双指针
策略：用最小的饼干去满足胃口最小的孩子，能满足就给，不满足就换更大的饼干。
步骤：
g、s都排序- 两个指针：
i指向当前孩子（从小胃口开始）j指向当前饼干（从小尺寸开始）
- 如果
s[j] >= g[i]：满足一个孩子，i += 1, j += 1 - 否则：饼干太小，只能换更大的饼干，
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):
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n + m log m) | 两次排序（n=len(g),m=len(s)）+ 一次双指针扫描 |
| 空间复杂度 | O(1)（不算排序） | 只用常数变量；若语言排序用额外空间则取决于实现 |
376. 摆动序列
目标：
给你一个整数数组nums，找一个最长子序列，满足：
- 相邻差值正负交替
nums=[1,7,4,9,2,5]diff=[+6,-3,+5,-7,+3]✅ 全程交替 答案=6 - 子序列不要求连续（可以跳着选）
👉 返回这个最长长度。
核心思路（贪心）
我们只关心“方向有没有变”，不关心数值具体多大。
只要方向变了，就一定能多摆一下。
我们同时维护两种“结尾状态”：
| 状态 | 意味着什么 |
|---|---|
| up | 当前这条序列最后一步是上升 |
| down | 当前这条序列最后一步是下降 |
我们在贪：尽可能多地制造“方向切换”
只在方向发生改变的时候更新：
如果今天比昨天高： 说明出现“上升” 那我可以接在“下降”后面 → 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)| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 一次遍历 |
| 空间复杂度 | O(1) | 只用两个变量 |
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| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 一次遍历 |
| 空间复杂度 | O(1) | 只用常数变量 |
