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()i0# 孩子指针当前要满足的孩子j0# 饼干指针当前可用的最小饼干count0whileilen(g)andjlen(s):# 当前饼干能满足当前孩子成功分配ifg[i]s[j]:i1j1count1else:# 饼干太小无法满足任何“更大胃口”的孩子# 只能丢掉这块饼干换下一块更大的j1returncount只要“孩子还没分完”并且“饼干还没用完”分配就有意义。少一个都不行。所以必须是whileilen(g)andjlen(s):项目复杂度说明时间复杂度O(n log n m log m)两次排序nlen(g),mlen(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: 以“下降”结尾的最长摆动子序列长度updown1foriinrange(1,len(nums)):ifnums[i]nums[i-1]:# 当前是上升 → 可以接在“下降”后面updown1elifnums[i]nums[i-1]:# 当前是下降 → 可以接在“上升”后面downup1else:# 相等则忽略不会形成摆动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_sumnums[0]# max_sum目前为止见过的最大子数组和max_sumnums[0]foriinrange(1,len(nums)):# 核心贪心要不要之前那段# 如果之前是负的直接丢掉从 nums[i] 重新开始cur_summax(nums[i],cur_sumnums[i])# 更新全局最大值max_summax(max_sum,cur_sum)returnmax_sum项目复杂度说明时间复杂度O(n)一次遍历空间复杂度O(1)只用常数变量