力扣题目：#860.柠檬水找零
刷题时长：30min
解题方法：分类讨论模拟
复杂度分析
- 时间
- 空间
问题总结
- 找零关键要看手里的钞票面值，并不是总和够了即能找零
- 15元找零可以用10+5 或者5+5+5
本题收获
- 分类模拟
- 情况一：账单是5，直接收下。
- 情况二：账单是10，消耗一个5，增加一个10
- 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
- 贪心思路：情况三中，美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能
- 局部最优：遇到账单20，优先消耗美元10，完成本次找零
- 全局最优：完成全部账单的找零。
力扣题目：#406.根据身高重建队列
刷题时长：参考题解
解题方法：贪心
复杂度分析
- 时间O(n^2)
- 空间
问题总结
- 无思路，无法实现
本题收获
- 二维数组排序的语法
-
# lambda返回的是一个元组：当-x[0](维度h）相同时，再根据x[1]（维度k）从小到大排序people.sort(key=lambda x: (-x[0], x[1])) -
# people已经排序过了：同一高度时k值小的排前面。for p in people:que.insert(p[1], p) - lambda匿名函数 + sort函数语法
- insert函数语法：list.insert(index, item_value)，insert操作复杂度为O(n^2)
-
- 贪心思路：先确定一个维度，就是身高，前面的节点一定都比本节点高。确定一边然后贪心另一边的k个前人，两边一起考虑，就会顾此失彼
-
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
-
全局最优：最后都做完插入操作，整个队列满足题目队列属性
-
力扣题目：#452. 用最少数量的箭引爆气球
刷题时长：参考答案后5min
解题方法：贪心+排序
复杂度分析
- 时间O(nlogn)，有一次快排
- 空间O(1)
问题总结
- 难以理解题意
本题收获
- 贪心思路：为了让气球尽可能的重叠，需要对数组进行排序。如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。
- 局部最优：当气球出现重叠，一起射，所用弓箭最少
- 全局最优：把所有气球射爆所用弓箭最少
