算法训练（leetcode）二刷第二十五天 | *134. 加油站、*135. 分发糖果、860. 柠檬水找零、*406. 根据身高重建队列

*134. 加油站

leetcode题目地址

当前站点可以剩余油量=gas[i] - cost[i];
将每站的剩余油量求和计算累计剩余油量，总剩余油量小于0，则无法行驶一周。
若在到达某一站时累计剩余油量为负时，则起始位置为i+1。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

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

*135. 分发糖果

leetcode题目地址

需要从左右两侧分别考虑而不是同时考虑。
额外开辟一个数组记录每个人的糖果数。

先从左向右查看右侧比左侧大的赋值比左侧的糖果多1。
再从右向左查看左侧比右侧大的赋值比右侧的糖果多1。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {public int candy(int[] ratings) {int[] candies = new int[ratings.length];Arrays.fill(candies, 1);for(int i=1; i<ratings.length; i++){if(ratings[i]>ratings[i-1]) candies[i] = candies[i-1]+1;}int sum = candies[ratings.length-1];for(int i=ratings.length-2; i>=0; i--){if(ratings[i]>ratings[i+1]) candies[i] = Math.max(candies[i+1]+1, candies[i]);sum += candies[i];}return sum;}
}

860. 柠檬水找零

leetcode题目地址

题目要求是立即为顾客找零，不可以等待。也就是说只能第一个顾客收5元第二个收10元，不允许第一个收10元第二个收5元。

因此只需要分别记录三种面值的数量，在收到一份钱后立刻找零，若某种面值出现负值，则说明找不开，返回false。若全程没有出现负值，则在最后返回true。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// java
class Solution {public boolean lemonadeChange(int[] bills) {int five=0, ten=0, twenty=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;}twenty++;}if(five<0 || ten<0 || twenty<0) return false;}return true;}
}

*406. 根据身高重建队列

leetcode题目地址

共有两个维度，h和k，分两次考虑，先考虑身高，对其由高向低排序，再考虑k，对其由小到大排序。

排序操作O(nlogn)，单元素插入指定位置操作O(n)，n个元素O(n²)。

时间复杂度： $O(nlogn+n^2)$
空间复杂度： $O(n)$

// java
class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a, b) -> {if(a[0] == b[0]) return a[1]-b[1];return b[0]-a[0];});LinkedList<int[]> que = new LinkedList<>();for (int[] p : people){// 将元素p插入p[1]位置que.add(p[1], p);}return que.toArray(new int[people.length][]);}
}