没做出来
class Solution {
public boolean lemonadeChange(int[] bills) {
int numFive = 0;
int numTen = 0;
//int numTwenty = 0;
for(int i = 0; i < bills.length; i++) {
if(bills[i] == 5) {
numFive ++;
} else if(bills[i] == 10) {
numTen ++;
numFive --;
} else if(bills[i] == 20) {
//numTwenty ++;
if(numTen > 0) {
numTen --;
numFive --;
} else {
numFive -= 3;
}
} //else return false;
if(numFive < 0 || numTen < 0) return false;//忘记判断
}
return true;
}
}排序：按照身高由高至低排列，身高相同的根据k由小到大排列
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性
class Solution {
public int[][] reconstructQueue(int[][] people) {
LinkedList<int[]> que = new LinkedList<>();
Arrays.sort(people, (a, b) -> {
if(a[0] == b [0]) return a[1] - b[1];//k升序
return b[0] - a[0];//h降序
});
//排序之后people[i] 前面的人身高都是大于等于hi 此时利用ki作为新数组的索引重新构造数组
for(int[] p : people) {
que.add(p[1], p);
}
return que.toArray(new int[people.length][]);
}
}将左边界进行排序，比较相邻区域是否有重叠，若无，射击次数加一，有，更新右边界
局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
class Solution {
public int findMinArrowShots(int[][] points) {
int res = 1;
Arrays.sort(points, (a,b) -> Integer.compare(a[0], b[0]));//根据左边界进行升序排序
for(int i = 1; i < points.length; i++) {
if(points[i - 1][1] < points[i][0]) res++;//相邻边界没有重叠，射击次数加一
else {
points[i][1] = Math.min(points[i][1], points[i - 1][1]);//重叠，更新最小右边界
}
}
return res;
}
}?