算法训练（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][]);
    }
}