此博客为《代码随想录》贪心算法章节的学习笔记，主要内容为贪心算法序列问题的相关题目解析。
文章目录
- 376. 摆动序列
- 738. 单调递增的数字
- 53. 最大子序和
- 122. 买卖股票的最佳时机 II
376. 摆动序列
题目链接
class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:n = len(nums)if n < 2: return ntrend = 0 # 记录之前的趋势 1 上升 -1 下降res = 1for i in range(1, n):if (trend == 0 or trend == 1) and nums[i] < nums[i-1]:trend = -1res += 1elif (trend == 0 or trend == -1) and nums[i] > nums[i-1]:trend = 1res += 1return res
- 贪心思路：仅统计趋势变换的次数，使用
trend变量记录之前的趋势，如果当前元素趋势更改，则更新trend和答案 - 根据题目定义，末尾元素默认算一次摆动，因此
res初始化为 1
738. 单调递增的数字
题目链接
class Solution:def monotoneIncreasingDigits(self, n: int) -> int:if n <= 9:return ndigits = [int(i) for i in list(str(n))]n = len(digits)flag = n # 记录从哪一位开始变成 9 for i in range(n - 1, 0, -1):if digits[i] < digits[i-1]:flag = idigits[i - 1] -= 1digits[flag:] = [9] * (n - flag)res = 0for num in digits:res = res * 10 + numreturn res
- 从后向前遍历，每当遇到
digits[i] < digits[i-1]，则表示i位置之后都需要变成 9；注意并不是只是将i位置变成 9，考虑例子 100，只修改i位置得到的答案为 90。 - 使用
flag进行记录，等遍历完毕后统一进行更改
53. 最大子序和
题目链接
class Solution:def maxSubArray(self, nums: List[int]) -> int:res = -infmin_pre_sum, pre_sum = 0, 0for n in nums:pre_sum += nres = max(res, pre_sum - min_pre_sum)min_pre_sum = min(min_pre_sum, pre_sum)return res
- 维护最小前缀和，用“当前前缀和 - 最小前缀和”，得到以当前元素为结尾的最大子序列和
- 更常用解法为动态规划
122. 买卖股票的最佳时机 II
题目链接
class Solution:def maxProfit(self, prices: List[int]) -> int:res = 0for i in range(1, len(prices)):if prices[i] > prices[i-1]:res += prices[i] - prices[i-1]return res
- 贪心策略：所有上涨交易日都买卖（赚到所有利润）