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

134. 加油站
题目链接：134. 加油站
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰加油站
日期：2024-10-04

想法：1.总汽油大于等于消耗一定能跑完，2.当前剩余汽油小于0了，只能从下一站开始重新计算
Java代码如下：

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;
        return index;
    }
}

135. 分发糖果
题目链接：135. 分发糖果
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰分发糖果
日期：2024-10-04

想法：两次贪心：一次是从左到右遍历，比较右边评分比左边大的情况，一次是从右到左遍历，比较左边评分比右边大的情况。
Java代码如下：

class Solution {
    public int candy(int[] ratings) {
        int[] candyVec = new int[ratings.length];
        candyVec[0] = 1;
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            }else{
                candyVec[i] = 1;
            }
        }
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i + 1] + 1, candyVec[i]);
            }
        }
        int res = 0;
        for(int candy : candyVec) {
            res += candy;
        }
        return res;
    }
}

总结：每次考虑一个方向才能不乱。

860.柠檬水找零
题目链接：860.柠檬水找零
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰柠檬水找零
日期：2024-10-04

想法：5, 10没有选择；20的话优先消耗10和5，如果没有10再消耗3张5
Java代码如下：

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++;
            }
            if(bills[i] == 10) {
                if(five <= 0) return false;
                five--;
                ten++;
            }
            if(bills[i] == 20) {
                if(five > 0 && ten > 0) {
                    five--;
                    ten--;
                }else if(five >= 3) {
                    five -= 3;
                }else {
                    return false;
                }
            }
        }
        return true;
    }
}

406.根据身高重建队列
题目链接：406.根据身高重建队列
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰根据身高重建队列
日期：2024-10-04

想法：按照从高往低排，再从前到后按K值插入。
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) {
            que.add(p[1],p);
        }
        return que.toArray(new int[people.length][]);
    }
}