第二十九天|贪心算法| 134. 加油站， 135. 分发糖果 ，860.柠檬水找零，406.根据身高重建队列
目录
134. 加油站
方法1：暴力方法--超时
方法2：贪心方法
135. 分发糖果（两次贪心）
860.柠檬水找零
406.根据身高重建队
134. 加油站
方法1：暴力方法--超时
暴力的方法很明显就是O(n^2)的，遍历每一个加油站为起点的情况，模拟一圈。
如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。
暴力的方法思路比较简单，但代码写起来也不是很容易，关键是要模拟跑一圈的过程。
for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {// 方法1：暴力方法 --> 超时了for (int i = 0; i < cost.length; i++) {int res = gas[i] - cost[i]; // 记录剩余油量int index = (i + 1) % cost.length;while (res > 0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）res += gas[index] - cost[index];index = (index + 1) % cost.length;}// 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置if (res >= 0 && index == i) return i;}return -1;}
}- 时间复杂度：
- 空间复杂度：
方法2：贪心方法
思路
如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
注意是如何更新下标的
局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。
注意：下面代码中的方法2是我一开始的想法，思路和方法3差不多，但是用两个for循环增加了时间复杂度，建议采用方法3的贪心，定义一个curSum和totalSum，两个变量就可以用一个for循环实现。
// 方法2：贪心（麻烦）
// int len = gas.length;
// int[] res = new int[len];
// int sum = 0;
// int index = -1;
// for (int i = 0; i < len; i++) {
// res[i] = gas[i] - cost[i];
// sum += res[i];
// }
// if (sum >= 0){
// int s = 0;
// index = 0;
// for (int i = 0; i < len; i++) {
// s += res[i];
// if (s < 0){
// index = (i + 1) % len;
// s = 0;
// }
// }
// }
// return index;// 方法3：贪心（设置2个sum替换一个for循环）int curSum = 0;int totalSum = 0;int index = 0;for (int i = 0; i < gas.length; i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {curSum = 0;index = (i + 1) % gas.length;}}if (totalSum < 0) {return -1;}return index;}}- 方法 2：时间复杂度为 O(n)，空间复杂度为 O(n)。
- 方法 3：时间复杂度为 O(n)，空间复杂度为 O(1)。
因为方法3只使用了常量，而方法2还定义了res数组，因此空间复杂度更高。
135. 分发糖果（两次贪心）
两次贪心的策略：
- 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
- 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。
- 先确定右边评分大于左边的情况（也就是从前向后遍历）
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1
- 再确定左孩子大于右孩子的情况（从后向前遍历）
遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？
因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果，所以 要从后向前遍历。
如果从前向后遍历，rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了 。
如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。
那么又要贪心了，局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
class Solution {public int candy(int[] ratings) {/**分两个阶段1、起点下标0 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 12、起点下标 ratings.length - 1 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大*/int[] count = new int[ratings.length];count[0] = 1;// 从左到右for (int i = 0; i < ratings.length - 1; i++) {count[i + 1] = (ratings[i] < ratings[i + 1]) ? (count[i] + 1) : 1;}// 从右到左for (int j = ratings.length - 1; j > 0; j--) {if (ratings[j] < ratings[j - 1]) {count[j - 1] = Math.max(count[j - 1], count[j] + 1);}}int sum = 0;for (int n : count){sum += n;}return sum;}
}- 时间复杂度: O(n)
- 空间复杂度: O(n)
860.柠檬水找零
只需要维护三种金额的数量，5，10和20。
有如下三种情况：
- 情况一：账单是5，直接收下。
- 情况二：账单是10，消耗一个5，增加一个10
- 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5。
class Solution {public boolean lemonadeChange(int[] bills) {int five = 0, ten = 0;for (int i = 0; i < bills.length; i++) {if (bills[i] == 5) {five++;} else if (bills[i] == 10) {five--;ten++;} else {if (ten > 0) {ten--;five--;} else {five -= 3;}}if (five < 0 || ten < 0) {return false;}}return true;}}- 时间复杂度: O(n)
- 空间复杂度: O(1)
406.根据身高重建队列
思路：本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列。
对于本题相信大家困惑的点是先确定k还是先确定h呢，也就是究竟先按h排序呢，还是先按照k排序呢？
如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。
那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！
那么只需要按照k为下标重新插入队列就可以了。
按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
例子：
回归本题，整个插入过程如下：
排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
插入的过程：
- 插入[7,0]：[[7,0]]
- 插入[7,1]：[[7,0],[7,1]]
- 插入[6,1]：[[7,0],[6,1],[7,1]]
- 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
- 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
- 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
此时就按照题目的要求完成了重新排列。
class Solution {public int[][] reconstructQueue(int[][] people) {// 身高从大到小排（身高相同k小的站前面）Arrays.sort(people, (a, b) -> {if (a[0] == b[0]) {return a[1] - b[1]; // a - b 是升序排列，故在a[0] == b[0]的状况下，会根据k值升序排列}return b[0] - a[0]; // b - a 是降序排列，在a[0] != b[0]，的状况会根据h值降序排列});LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {que.add(p[1], p); //Linkedlist.add(index, value)，会将value插入到指定index里}return que.toArray(new int[people.length][]);}}注意：Linkedlist.add(index, value)，会将value插入到指定index里
第二十九天的总算是结束了，直冲Day30！