860.柠檬水找零
题目链接/文字讲解：柠檬水找零
题设：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
思路：简单题，每次尽可能多用10块钱即可。
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 == 0) return false;
five--;
ten++;
}else {
if (ten>0&&five>0){
ten--;
five--;
}else if (five>=3){
five-=3;
}else return false;
}
}
return true;
}
406.根据身高重建队列
题目链接/文字讲解：根据身高重建队列
题设：假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
思路：遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。如果两个维度一起考虑一定会顾此失彼。首先按照K排序，发现啥也没确定。按照H排序，身高一定是从大到小排（身高相同的话则k小的站前面）。
可以放心插入的原因，每组人之前都必定至少有k个h大于等于他的人。局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性；全局最优：最后都做完插入操作，整个队列满足题目队列属性。
for循环冒号的用法：用一个变量代替数组中的元素。
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1];//k要升序
return b[0] - a[0];//h要降序
});
LinkedList<int[]> queue = new LinkedList<>();
for (int[] p:people){
queue.add(p[1],p);//.add(index, value)，會將value插入到指定index裡。
}
return queue.toArray(new int[people.length][]);
}
}
注意点：lambda表达式以及linkedlist的使用。
452. 用最少数量的箭引爆气球
题目链接/文字讲解：用最少数量的箭引爆气球
题设：有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
思路：局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。思路简单，但是实现射气球的过程挺难。复杂的做法是每次射完一个气球后就移除一个元素；但如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，只要记录一下箭的数量就可以了。
按照气球起始位置排序，如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。
注意点：两个气球挨在一起不重叠也可以一起射爆。如果数组不为0则至少需要一个，因此射箭数从1开始往上加。同时遍历的起点也应该从数组的第二个值开始，因为第一个气球一定需要一支箭来射爆它。
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int count = 1;
for (int i = 1; i < points.length; i++) {
if (points[i - 1][1] < points[i][0]) {
count++;
} else {
points[i][1] = Math.min(points[i - 1][1], points[i][1]);
}
}
return count;
}
}
数组排序需要采用Integer内置比较方法，才不会溢出。
