代码随想录算法训练营 Day 23
Published:
贪心算法
解题步骤：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
Q1. LeetCode 455
用大饼干满足大胃口的孩子，用小饼干满足小胃口的孩子
注意两种解法的区别（遍历数组）
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
res = 0
idx = len(s) - 1
for i in range(len(g) - 1, -1, -1):
if idx >= 0 and s[idx] >= g[i]:
res += 1
idx -= 1
return res
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
res = 0
idx = 0
for i in range(len(s)):
if idx < len(g) and s[i] >= g[idx]:
res += 1
idx += 1
return res
复杂度分析
时间复杂度：O($nlogn$) 空间复杂度：O(1)
Q2. LeetCode 376
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums) == 1:
return 1
curr_diff = 0
prev_diff = 0
res = 1
for i in range(len(nums) - 1):
curr_diff = nums[i + 1] - nums[i]
if (curr_diff < 0 and prev_diff >= 0) or (prev_diff <= 0 and curr_diff > 0):
res += 1
prev_diff = curr_diff
return res
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
Q3. LeetCode 53
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = float('-inf')
n = len(nums)
s = 0
for num in nums:
s += num
if s > res:
res = s
if s <= 0:
s = 0
return res
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
TODO
理解贪心算法，掌握动态规划解法