贪心算法
- 贪心算法介绍
- 1. 柠檬水找零
- 2. 将数组和减半的最少操作次数
- 3. 最大数
- 4. 摆动序列(贪心思路)
- 5. 最长递增子序列(贪心算法)
- 6. 递增的三元子序列
- 7. 最长连续递增序列
- 8. 买卖股票的最佳时机
- 9. 买卖股票的最佳时机Ⅱ(贪心算法)
- 10. K 次取反后最大化的数组和
- 11. 按身高排序
- 12. 优势洗牌
- 13. 最长回文串
- 14. 增减字符串匹配
- 15. 分发饼干
- 16. 最优除法
- 17. 跳跃游戏Ⅱ
- 18. 跳跃游戏
- 19. 加油站
- 20. 单调递增的数字
贪心算法介绍
什么是贪心算法呢？
首先，我们需要知道贪心策略，即解决问题的策略，将局部最优转变为全局最优；
- 把解决问题的过程分为若干步；
- 解决每一步的时候，都选择当前看起来"最优的"解法；
- "希望"得到全局最优解
贪心算法的特点：
- 提出贪心策略，但是贪心策略的提出是没有标准和模板的，可能每一道题的贪心策略都是不同的；
- 贪心策略的正确性没有保障，因为我们提出的"贪心策略"有可能是错误的，正确的贪心策略是需要"证明的"；常用的证明方法是我们学过的数学中见过的证明方法。
下面我们结合题目进行分析。
1. 柠檬水找零
题目链接 -> Leetcode -860.柠檬水找零
Leetcode -860.柠檬水找零
题目：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5, 5, 5, 10, 20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5, 5, 10, 10, 20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
- 1 Leetcode -2208.将数组和减半的最少操作次数
Leetcode -2208.将数组和减半的最少操作次数
题目：给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
示例 1：
输入：nums = [5, 19, 8, 1]
输出：3
解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法：
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为[5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33 / 2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。
示例 2：
输入：nums = [3, 8, 20]
输出：3
解释：初始 nums 的和为 3 + 8 + 20 = 31 。
以下是将数组和减少至少一半的一种方法：
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为[1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31 / 2 = 15.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。
提示：
- 1
