海智算法训练营第三十四天 | 第八章 贪心算法 part04 | ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球

��今日任务：

1.贪心算法找零

2.双维度问题解法

3.判断重叠区间问题

1.贪心算法找零

力扣题目链接

这道题较简单，就是分清情况区别对待就ok了

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

  所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。 

  class Solution {    public boolean lemonadeChange(int[] bills) {        int five = 0 , ten = 0;        for(int temp : bills){            if(temp == 5)   five++;            else if(temp == 10){                if (five  0 && ten > 0){                    five--;                    ten--;                } else if (five >= 3){                    five-=3;                }else return false;            }        }        return true;    }}

  2.双维度问题解法

  力扣题目链接

  遇到两个维度的问题的时候一定要先确定一个维度再确定另外一个维度

  按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

  此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

  那么只需要按照k为下标重新插入队列就可以了，为什么呢？

  看图：

  先以身高维度排序，再按照题目位置条件调整位置，因为排序后的前面比你高的数是固定的，所以移动不会影响到其他的位置上的数。

  class Solution {    public int[][] reconstructQueue(int[][] people) {        Arrays.sort(people , (o1,o2)->o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);        LinkedList que = new LinkedList();        for(int[] p : people){            que.add(p[1] , p);        }        return que.toArray(new int[people.length][people.length]);    }}

  3.判断重叠区间问题

  力扣题目链接c 

  class Solution {    public int findMinArrowShots(int[][] points) {        Arrays.sort(points , (o1,o2) -> Integer.compare(o1[0],o2[0]));        int count = 1 ;//初始至少有一支箭        for (int i = 1; i  points[i-1][1])   count++;            else{                points[i][1] = Math.min(points[i-1][1] , points[i][1]);            }        }        return count;    }}

  此题的关键就在于如何简单理解，先把区间按照左边界排序，这时候就分以下几种情况：

  1.区间的左边界比上个区间的右边界要大，这时候两区间不重叠至少加一箭

  2.区间的左边界小于等于上个区间的右边界，这时候需要更新当前区间的右边界，选择重叠区间中更小的右边界，因为这样区间更大的以及包含住了区间更小的，所以下个区间要是小于这个右边界，那么理所当然和上上个边界也是重合的。

   

  学习时长：2h

  总结：此次的学习到了关于双维度、区间重叠的贪心做法，从局部到全局，对此类的题型更加熟悉