基础算法—贪心篇
什么是贪心
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
贪心的套路（什么时候用贪心）
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优，推出整体最优。
贪心一般解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
455. 分发饼干
思路
376. 摆动序列
思路
53. 最大子数组和
思路
1005. K 次取反后最大化的数组和
思路
860. 柠檬水找零
思路
738. 单调递增的数字
思路
122. 买卖股票的最佳时机 II
思路
55. 跳跃游戏
思路
714. 买卖股票的最佳时机含手续费
思路
135. 分发糖果
思路
406. 根据身高重建队列
思路
45. 跳跃游戏 II
思路
452. 用最少数量的箭引爆气球
思路
435. 无重叠区间
763. 划分字母区间
思路
56. 合并区间
思路
134. 加油站
思路
968. 监控二叉树
思路
基础算法—贪心篇
https://yztldxdz.top/2022/11/25/基础算法—贪心篇/