代码随想录 Day-23（贪心算法）
目录
思路
错误解法
正确解法
力扣题目 406.根据身高重建队列
思路
力扣题目 452.用最少数量的剪引爆气球
思路
咋眼一看好像很复杂，分析清楚之后，会发现逻辑其实非常固定。这道题目可以告诉大家，遇到感觉没有思路的题目，可以静下心来把能遇到的情况分析一下，只要分析到具体情况了，一下子就豁然开朗了。
如果一直陷入想从整体上寻找找零方案，就会把自己陷进去，各种情况一交叉，只会越想越复杂。
分析情况如下：
- 直接收5元
- 收10元，消耗5元
- 收20元，消耗10元+5元，或者3个5元
策略上已经可以是固定，只用情况三具有不确定性，所以对于20元时候，优先用10+5去找零，再去用5找零，原因是其万能找零。
所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
错误解法
当数组为 [5,5,5,5,20,20,5,5,5,5] ，这里其实是false，不是true的。因此是一旦手中没有零钱找零就是false，不能后来再补上，因此需要在循环里面做判断，一旦出现负数就是false。
public boolean lemonadeChange(int[] bills) { int ten = 0; int five = 0; for (int bill : bills) { if (bill == 5) { five++; } else if (bill == 10) { ten++; five--; } else if (bill == 20) { if (ten > 0 ) { ten--; five--; } else { five -= 3; } } } return five >= 0 && ten >= 0; }正确解法
力扣题目 406.根据身高重建队列
思路
这里可以看出来是有两个维度考虑，和力扣题目 135.分发糖果（可以看我day-22的文章） 有点类似。
因此遇到这种两个维度权衡的时候，一定是先考虑一个维度再按照另一个维度来重新考虑排序。
两个维度一起考虑一定会顾此失彼。
- 局部最优：优先按身高来排序，再按照k的大小来排序
- 全局最优：最后完成按k插入操作，整个队列，满足题目队列的属性
class Solution { public int[][] reconstructQueue(int[][] people) { //先按身高来排序 Arrays.sort(people, (o1,o2)->{ //h升高相同时 if(o1[0] == o2[0]) return o1[1] - o2[1]; //这里是当h身高相同时，按k的升序排序 //h身高不相同时，则按降序来排序 return o2[0] - o1[0]; }); LinkedList<int[]> queue = new LinkedList<>(); for(int[] person : people){ //LinkedList.add(index, value)，会将value 插入到指定index里 queue.add(person[1],person); } //记得转化为数组 return queue.toArray(new int[people.length][]); } }Tips：
对于插入和删除操作，LinkedList优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引
要是对Lambda表达式不熟悉的可以点击下方链接跳转学习
JDK之Arrays的Lambda表达式
力扣题目 452.用最少数量的剪引爆气球
class Solution { public int findMinArrowShots(int[][] points) { //做一个剪枝 if(points.length == 0) return 0; //首先按照start来排序 Arrays.sort(points, (o1, o2) -> //{return o1[0] - o2[0];} //按照start的升序来排序 Integer.compare(o1[0], o2[0]) ); //因为是i与i-1比较，所以需要i初始值为1，才不会出现负值 //既然i初始值不为0，那么result初始值应该是1 int result = 1; //i的start的与i-1的end比较 for(int i=1; i<points.length; i++){ if(points[i][0] > points[i-1][1]) result ++; else //不然就是小于等于的情况，所以更新重叠气球的最小右边界，判断下一个是否重叠 points[i][1] = Math.min(points[i][1], points[i-1][1]); } return result; } }要是对Lambda表达式不熟悉的可以点击下方链接跳转学习
JDK之Arrays的Lambda表达式