代码随想录算法训练营第29天|LeetCode 134. 加油站、135. 分发糖果、860.柠檬水找零、406.根据身高重建队列

1. LeetCode 134. 加油站

题目链接：https://leetcode.cn/problems/gas-station/description/
文章链接：https://programmercarl.com/0134.加油站.html
视频链接：https://www.bilibili.com/video/BV1jA411r7WX

思路：
贪心：
局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。
全局最优：找到可以跑一圈的起始位置。

如果从起始位置i开始跑一圈的过程中不出现累加和curSum小于0的情况就说明该起始位置i可以跑一圈。若出现，则说明起始位置i到出现累加和小于0的位置j之间不存在合适的起始位置，新的起始位置从j+1开始。

解法：
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int start = 0;int curSum = 0;int totalSum = 0;for (int i=0;i<gas.length;i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {start = i + 1;curSum = 0;}}if (totalSum < 0) {return -1;}return start;}
}

代码解析：
有一个关键的变量，即：totalSum。用其判断整个数组有没有起始位置，若小于0，则表示没有起始位置；若大于0，则表示有起始位置。
在如下for循环中只需要判断半圈是否是有起始位置就可以，因为另一半肯定没有。
如，在i位置的curSum<0，则说明[0,i]区间内肯定没有起始位置，则从i+1开始考虑，若[i+1,gas.length-1]区间内不出现curSum小于0的情况，注意：此时只考虑了半圈，说明在该区间内不出现新的起始位置，只考虑i+1位置就行。
但是，i+1只是有可能是正确的，因为它完全可能在另一半圈[0,i]累加求和中出现curSum小于0的情况。这时就要看totalSum，若小于0，说明没有起始位置，i+1作为起始位置也不行；若大于0，说明有起始位置，i+1可以作为起始位置。

for (int i=0;i<gas.length;i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {start = i + 1;curSum = 0;}
}

2. LeetCode 135. 分发糖果

题目链接：https://leetcode.cn/problems/candy/description/
文章链接：https://programmercarl.com/0135.分发糖果.html
视频链接：https://www.bilibili.com/video/BV1ev4y1r7wN

思路：
本题关键：处理好一边再处理另一边，不要两边想着一起兼顾。
采用两次贪心的策略：
1️⃣一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
局部最优：只要右边评分比左边大，右边的孩子就多一个糖果；
全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。
2️⃣一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。
全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。

解法：
class Solution {public int candy(int[] ratings) {int[] candy = new int[ratings.length];for (int i=0;i<candy.length;i++) {candy[i] = 1;}// 从前往后遍历 比较右孩子评分大于左孩子的场景for (int i=0;i<ratings.length-1;i++) {if (ratings[i] < ratings[i+1]) {candy[i+1] = (candy[i]+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();}
}

3. LeetCode 860.柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/description/
文章链接：https://programmercarl.com/0860.柠檬水找零.html
视频链接：https://www.bilibili.com/video/BV12x4y1j7DD

思路：
本题关键：只需要维护三种金额的数量：5，10和20。
存在 如下三种情况：
情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
账单是20的情况，为什么要优先消耗一个10和一个5呢？
因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

贪心：
局部最优：遇到账单20，优先消耗美元10，完成本次找零。
全局最优：完成全部账单的找零。

class Solution {// public boolean lemonadeChange(int[] bills) {//     if (bills[0] > 5) {//         return false;//     }//     Map<String,Integer> map = new HashMap<>();//     map.put("5",0);//     map.put("10",0);//     map.put("20",0);//     for (int i=0;i<bills.length;i++) {//         if (bills[i] == 5) {//             map.put("5",map.get("5")+1);//         } else if (bills[i] == 10) {//             if (map.get("5") <= 0) {//                 return false;//             } else {//                 map.put("5",map.get("5")-1);//             }//             map.put("10",map.get("10")+1);//         } else if (bills[i] == 20) {//             if (map.get("5") <= 0) {//                 return false;//             } else if (map.get("10") <= 0 && map.get("5") < 3) {//                 return false;//             } else if (map.get("10") > 0) {//                 map.put("10",map.get("10")-1);//                 map.put("5",map.get("5")-1);//             } else if (map.get("5")>=3) {//                 map.put("5",map.get("5")-3);//             }//             map.put("20",map.get("20")+1);//         }//     }//     return true;// }public boolean lemonadeChange(int[] bills) {if (bills[0] > 5) {return false;}Map<String,Integer> map = new HashMap<>();map.put("5",0);map.put("10",0);map.put("20",0);int num5 = 0;int num10 = 0;int num20 = 0;for (int i=0;i<bills.length;i++) {if (bills[i] == 5) {num5++;} else if (bills[i] == 10) {if (num5 <= 0) {return false;} else {num5--;}num10++;} else if (bills[i] == 20) {if (num10 > 0 && num5 > 0) {num10--;num5--;} else if (num5 >= 3) {num5 = num5 - 3;} else {return false;}num20++;}}return true;}    
}

4. LeetCode 406.根据身高重建队列

题目链接：https://leetcode.cn/problems/queue-reconstruction-by-height/description/
文章链接：https://programmercarl.com/0406.根据身高重建队列.html
视频链接：https://www.bilibili.com/video/BV1EA411675Y

思路：
本题关键：本题有两个维度，h和k。确定一个维度，然后再按照另一个维度重新排列。
首先按照身高排序，然后优先按身高高的people的k来插入，后续插入节点即便插入到了已经插入节点的前边，也不会影响前面已经插入的节点，最终按照k的规则完成了队列。（后续插入的节点的身高始终低于前面已经插入的节点的身高，即便插入到前边，不影响前面已经插入节点的k值）

按照身高从大到小排序后：
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性

注意：按照身高排序时，若身高相同，则优先将k小的排在前面。

解法：
class Solution {public int[][] reconstructQueue(int[][] people) {// 1.先按照身高进行降序排序，然后按照k进行升序排序Arrays.sort(people,(a,b) -> {if (a[0] == b[0]) return a[1]-b[1];return b[0]-a[0];});LinkedList<int[]> queue = new LinkedList<>();// 2. 向前插入for (int[] p:people) {queue.add(p[1],p);}return queue.toArray(new int[people.length][]);}
}