【力扣一刷】代码随想录day35（贪心算法part4：860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球 ）

目录

【860.柠檬水找零】简单题(很简单)

【406.根据身高重建队列】中等题（掌握思路后简单）

【452. 用最少数量的箭引爆气球】中等题

【860.柠檬水找零】简单题(很简单)

思路：

• 5元的直接收，不需要找钱
• 10元的只需要找5元
• 20元的优先找10元，没有10元再全部找5元

class Solution {public boolean lemonadeChange(int[] bills) {int five = 0;int ten = 0;for (int i = 0; i < bills.length; i++){if (bills[i] == 5){five++;}else if (bills[i] == 10){if (five >= 1){five--;ten++;}else return false;}else{// 如果是付了20，则需要找15元，优先找10元if (ten >= 1 && five >= 1){ten--; // 10元1张five--; // 5元1张}else if (five >= 3){five -= 3; // 5元3张}else return false;}}return true;}
}

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

【406.根据身高重建队列】中等题（掌握思路后简单）

思路：先按身高 h 从大到小排序，再依照 k 调整顺序

关键：按照身高降序排序后，即使将后面的数组调整到前面，也不会影响前面的 k ，因为前面的肯定比后面的高。

示例：

class Solution {public int[][] reconstructQueue(int[][] people) {// 先按身高h降序排序，身高相同的情况下，按k升序排序Arrays.sort(people, (o1, o2) -> {int res = Integer.compare(o2[0], o1[0]); // h降序if (res != 0) return res;else return Integer.compare(o1[1], o2[1]); // k升序});// 频繁按索引插入，LinkedList（基于链表）的效率高于ArrayList（基于数组）List<int[]> list = new LinkedList<>(); for (int i = 0; i < people.length; i++){list.add(people[i][1], people[i]);  // 按照k调整，相当于从左到右按k为索引在链表中插入对应数组}return list.toArray(new int[people.length][]); // 链表 -> 数组，返回数组，注意要指定数组的类型和长度}
}

• 时间复杂度: O(nlogn)，快速排序
• 空间复杂度: O(n)，额外的链表空间消耗

总结：

1、排序需要重写compare方法，先按身高h降序排序，身高相同的情况下，再按k升序排序

2、调整顺序如果用ArrayList实现，时间复杂度会偏高，最好用LinkedList，而且要想到按k调整顺序相当于按k为索引，依次将people排序后的各个数组插入链表。

3、链表转换为数组的时候，注意toArray()方法默认返回的是Object[]型数组，需要在参数列表中用构造器指定数组的类型和长度。

【452. 用最少数量的箭引爆气球】中等题（偏简单）

思路：

1、按气球的起始位置（左边界）排序

2、使用变量shoot记录上一支箭的范围，判断当前遍历的气球范围是否与上一支箭的范围存在重叠区域：

• 不存在重叠区域：需要增加一支箭，shoot更新为当前遍历的气球范围。
• 存在重叠区域：不需要增加箭，只更新shoot的范围，起始位置不变，结束位置取上一个shoot的结束位置和当前遍历气球的结束位置的最小值。

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));int[] shoot = points[0]; // 用于记录上一次射箭的范围int res = 1; // 至少有一个气球，至少射1支箭，初始化为1for (int i = 1; i < points.length; i++){// 必然成立shoot[0] < point[0]int[] point = points[i];// 当前遍历的气球不在上一支箭的范围内，需要多加一支箭，并更新射箭的范围if (shoot[1] < point[0]){res++;shoot = point;}// 当前遍历的气球在上一支箭的范围内，需继续用上一支箭即可，缩窄上一支箭的范围else {shoot[0] = point[0];shoot[1] = Math.min(shoot[1], point[1]);}}return res;}
}

• 时间复杂度: O(nlogn)，快速排序
• 空间复杂度: O(1)