134. 加油站
思路：
暴力解法：for循环适合模拟从头到尾的遍历，while循环适合模拟环形遍历！但是会超出leetcode的时间限制。
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {for(int i=0;i<gas.length;i++){int rest=gas[i]-cost[i];int index=(i+1)%gas.length;while(rest>0 && index!=i){ rest+=gas[index]-cost[index];index=(index+1)%gas.length;}if(rest>=0 && index==i) return i;}return -1;}
}
贪心算法：计算每个地点的剩余油量，如果剩余油量的累加和小于零，则说明0-i作为起点均不能绕环一周，从i+1开始，重新进行剩余油量的累加。如果剩余油量全部加起来小于0，说明不够一周，返回-1；否则一定存在index使得能够环绕一周。
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {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){index=i+1;curSum=0;}}if(totalSum<0) return -1;else return index;}
}
135. 分发糖果
思路：设置一个数组来存储分发的糖果量，令0处的糖果数为1，先从0开始遍历右边，如果右边大，则右边的为左边的糖果数加一，否则为1；在从后往前遍历，如果左边的比右边的大，要选择右边的数+1和当前值更大的那个，才能保证两边条件都满足，否则当前糖数不变。
代码如下：
class Solution {public int candy(int[] ratings) {int[] candy=new int[ratings.length];candy[0]=1;for(int i=0;i<candy.length-1;i++){if(ratings[i+1]>ratings[i]) candy[i+1]=candy[i]+1;else candy[i+1]=1;}for(int i=candy.length-1;i>0;i--){if(ratings[i-1]>ratings[i]) candy[i-1]=Math.max(candy[i]+1,candy[i-1]);}int result=0;for(int i:candy) result+=i;return result;}
}
860.柠檬水找零
思路：这个题比较简单，直接分情况讨论就好，如果是5直接收下；如果是10，5减去一个；如果是20，先用10元找零，没有10了再考虑用3个5找零（体现贪心：优先使用作用有限的）
代码如下：
class Solution {public boolean lemonadeChange(int[] bills) {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((num5<=0) ||(num5<=2 && num10<=0)) return false;else if(num10>0){num20++;num10--;num5--;}else{num20++;num5=num5-3;}} }return true;}
}
考虑代码优化，最后判断5和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) {five--;ten++;} else if (bills[i] == 20) {if (ten > 0) {ten--;five--;} else {five -= 3;}}if (five < 0 || ten < 0) return false;}return true;}
}
406.根据身高重建队列
思路：首先这道题理解题意就理解了很久，意思是身高为h的人前面有k个人，需要按照身高重新排列来满足k。和糖果分发题目一样，技巧都是确定一边然后贪心另一边，两边一起考虑，就会顾此失彼。如果按照k的大小来排序，得到的结果还是无序的，意义不大，所以按照身高h来排序。
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性
代码如下：
class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)->{if(a[0]==b[0]) return a[1]-b[1];//如果h相同，k按升序排序else return b[0]-a[0];});LinkedList<int[]> queue=new LinkedList<>();for(int[] p:people){queue.add(p[1],p);}return queue.toArray(new int[people.length][]);}
}
总结：这个题目比较难，需要着重注意一下。