力扣题目：#1005.K次取反后最大化的数组和
刷题时长：10min
解题方法：贪心
复杂度分析
- 时间O(n)
- 空间O(1)
问题总结文章来源：https://www.toymoban.com/news/detail-492538.html
无
本题收获文章来源地址https://www.toymoban.com/news/detail-492538.html
- 贪心思路：两次贪心
- 在包含正负无序的整数数组中，如何转变K次正负，让数组和达到最大
- 局部最优：让绝对值大的负数变为正数，当前数值达到最大
- 整体最优：整个数组和达到最大
- 有序正整数序列，如何转变K次正负，让数组和达到最大
- 局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大
- 全局最优：整个数组和达到最大
- 在包含正负无序的整数数组中，如何转变K次正负，让数组和达到最大
- Python语法：用lambda表达式按绝对值降序排序 nums.sort(key=lambda x=abs(x), reverse=True)
力扣题目：#134. 加油站
刷题时长：参考答案后15min
解题方法：贪心
复杂度分析
- 时间O(n)
- 空间O(1)
问题总结
- 因为从index0开始跑起，答案初始化的值应为 0
本题收获
- 贪心思路
- 局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行
- 全局最优：找到可以跑一圈的起始位置
力扣题目：#135. 分发糖果
刷题时长：参考答案后15min
解题方法：贪心
复杂度分析
- 时间O(n)
- 空间O(n)
问题总结
- candy数量应基于被比较的candy数量上+1，而非自己原本的candy数量上+1
- 第二遍倒序比较时，candy被赋的值应在原有逻辑上再与当前值比较后，选大的值
- Python语法：数组中倒叙遍历应为 range(n, -1, -1)
本题收获
- 贪心思路：确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼
- 从左到右遍历，只比较右边孩子评分比左边大的情况
- 局部最优：只要右边评分比左边大，右边的孩子就多一个糖果
- 全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
- 从右到左遍历，只比较左边孩子评分比右边大的情况
- 局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的
- 全局最优：相邻的孩子中，评分高的孩子获得更多的糖果
- 从左到右遍历，只比较右边孩子评分比左边大的情况
到了这里，关于力扣算法刷题Day34｜贪心：K次取反后最大化的数组和 加油站 分发糖果的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
