java算法day35 | 贪心算法 part04 ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球

860.柠檬水找零

思路： 设定三个变量存储已有的三种面额的数量，只需要设想出每一种情况的找零方案，更新当前每种面额的数量。

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int count5=0;
        int count10=0;
        int count20=0;
        for(int i=0;i<bills.length;i++){
            if(bills[i]==5) count5++;
            if(bills[i]==10){
                count5--;
                count10++;
            }
            if(bills[i]==20){
                if(count10!=0){
                    count10--;
                    count5--;
                    count20++;
                }else{
                    count5=count5-3;
                }
            }
            if(count5<0) return false;
        }
        return true;
    }
}

时间复杂度: O(n)
空间复杂度: O(1)

406.根据身高重建队列

思路： 不能做到同时考虑两个维度，就先考虑身高，再考虑前面的人数。按身高降序排序，确保当前元素的前面都是比自己高的。再遍历数组，按照前面的人数插入到指定位置。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(o1,o2)->{
            if(o1[0]==o2[0]) return o1[1]-o2[1];//如果身高相同，根据k升序排列
            else{
                return o2[0]-o1[0];//身高高的人在前
            }
        });
        List<int[]> queue=new LinkedList<>();
        for(int[] i:people){
            queue.add(i[1],i);
        }
        return queue.toArray(new int[people.length][]);
    }
}

时间复杂度：O(nlog n + n)
空间复杂度：O(n)

452. 用最少数量的箭引爆气球

思路： 先升序排序，再根据重合与否增加箭数。注意排序中一定要使用Integer.compare(a[0],b[0])，否则会溢出。

class Solution {
    public int findMinArrowShots(int[][] points) {
        //注意，这里一定要使用Integer.compare(a[0],b[0])，否则会溢出
        Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
        int result=1;//points不为空至少需要一只箭
        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;
    }
}

时间复杂度：O(nlog n)，因为有一个快排
空间复杂度：O(1)，有一个快排，最差情况(倒序)时，需要n次递归调用。因此确实需要O(n)的栈空间