1.135. 分发糖果

思路：贪心。分两步走：

（1）从前向后遍历，确定右边评分大于左边的情况。此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果。 全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。

（2）从后向前遍历，确定左边评分大于右边的情况（不从后往前遍历会出错，因为如果是递减序列会有值为0的情况）。局部最优：取candy[i + 1] + 1 和 candy[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

public int candy(int[] ratings) {/**分两个阶段1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 12、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大*/int[] candy = new int[ratings.length];candy[0] = 1;for (int i = 1; i < ratings.length; i++) {// 这里有必要对右边＜左边的值赋为1candy[i] = ratings[i] > ratings[i - 1] ? candy[i - 1] + 1 : 1;}for (int i = ratings.length - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candy[i] = Math.max(candy[i], candy[i + 1] + 1);}}
// 最后返回和return Arrays.stream(candy).sum();
}

2.860. 柠檬水找零

思路：贪心。 其实对这三种进行判断即可：

• 情况一：账单是5，直接收下。

• 情况二：账单是10，消耗一个5，增加一个10

• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5。

for循环挨个进行判断。最后对five和ten判断是否＜0即可。

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) {five--;ten++;}else if (bills[i] == 20){if (ten > 0){five--;ten--;}else{five -= 3;}}if (five < 0 || ten < 0)return false;}return true;
}

3.406. 根据身高重建队列

思路：贪心。先按照身高降序排序，再优先按身高高的people的k升序来插。

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

注意：先身高降序排，后身高相同的人的k升序排。

class Solution {public int[][] reconstructQueue(int[][] people) {// 先进行排序：身高从大到小排，身高相同k小的在前面/**原 顺 序：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]一轮排序：[[7,0],[7,1],[5,0],[6,1],[5,2],[4,4]]二轮排序：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]*/Arrays.sort(people, (a, b) -> {// a[0]和b[0] 代表people的第一维，也就是身高；a[1]和b[1]是身高相同的k，是people第二维// 若身高相同，将k值小的排在前面 冒泡排序，若a[1] - b[1] > 0, 则进行交换，b挪到前面，否则位置不变if (a[0] == b[0]) return a[1] - b[1]; // a[1] - b[1]代表升序// 若身高不同，高个子排在前面 冒泡排序，若b[0] - a[0] > 0, 则进行交换b挪到前面，否则位置不变else return b[0] - a[0]; //否则身高高的在前降序排});// 构建队列List queue = new ArrayList<>();// 插入队列 按照k值插入对应位置/**排序后的数组：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]开始插入[[7,0]][[7,0],[7,1]][[7,0],[6,1],[7,1]][[5,0],[7,0],[6,1],[7,1]][[5,0],[7,0],[5,2],[6,1],[7,1]][[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]插入完毕*/for (int[] p : people) queue.add(p[1], p);// 队列转换成二维数组return queue.toArray(new int[people.length][]);}
}