算法训练营day28--134. 加油站 +135. 分发糖果+860.柠檬水找零+406.根据身高重建队列

一、 134. 加油站

题目链接：https://leetcode.cn/problems/gas-station/
文章讲解：https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
视频讲解：https://www.bilibili.com/video/BV1jA411r7WX

1.1 初见思路

1. 得模拟分析出，先计算每个加油站的汽油数量和消耗汽油数量的差值，再进行后续的分析

1.2 具体实现

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) {// 当前累加rest[i]和 curSum一旦小于0
                index = (i + 1) % gas.length ; // 起始位置更新为i+1
                curSum = 0; // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return index;
    }
}

1.3 重难点

• 这个题目不太好模拟

二、 135. 分发糖果

题目链接：https://leetcode.cn/problems/candy/
文章讲解：https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
视频讲解：https://www.bilibili.com/video/BV1ev4y1r7wN

2.1 初见思路

1. 首先找到评分最低的孩子，从他们开始分一个糖果
2. 再逐个向两边扩散

2.2 具体实现

class Solution {
/**
         分两个阶段
         1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
         2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
    */
    public int candy(int[] ratings) {
        int length = ratings.length;
        int[] arr = new int[length];
        int result=0;
        Arrays.fill(arr,1);
        for(int j=0;j<length-1;j++){
            if(ratings[j+1]>ratings[j]){
                arr[j+1]=arr[j]+1;
            }
        }
        for(int j=length-2;j>=0;j--){
            if(ratings[j]>ratings[j+1]){
                arr[j]=Math.max(arr[j+1]+1,arr[j]);
            }
        }
        for(int i=0;i<length;i++){
            result+=arr[i];
        }
        //int result = Arryas.sum(arr);
        return result;
    }
}

2.3 重难点

• 不能在考虑局部的时候想两边兼顾，这样会顾此失彼；
• 采用了两次贪心的策略，一次是从左到右遍历，只比较右边孩子评分比左边大的情况、一次是从右到左遍历，只比较左边孩子评分比右边大的情况

三、 860.柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/
文章讲解：https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html
视频讲解：https://www.bilibili.com/video/BV12x4y1j7DD

3.1 初见思路

1. 目的是找零，设置三个数来统计三种面额的钱的剩余数量
2. 找零的优先顺序是先找面额大的，也就是10美元，没有10美元再找5美元的

3.2 具体实现

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int fiveNum=0;
        int tenNum=0;
        for(int i=0;i<bills.length;i++){
            if(bills[i]==5){
                fiveNum++;
            }
            if(bills[i]==10){
                if(fiveNum==0){
                    return false;
                }
                fiveNum--;
                tenNum++;
            }
            if(bills[i]==20){
                if(tenNum>0 && fiveNum>0){
                    tenNum--;
                    fiveNum--;
                }
                else if(tenNum==0 && fiveNum>=3){
                    fiveNum-=3;
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }
}

3.3 重难点

四、 406.根据身高重建队列

题目链接：https://leetcode.cn/problems/queue-reconstruction-by-height/
文章讲解：https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html
视频讲解：https://www.bilibili.com/video/BV1EA411675Y

4.1 初见思路

1. 需要考虑两个因素，身高和k，所以需要 控制变量，先按照身高排序

4.2 具体实现

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 身高从大到小排（身高相同k小的站前面）
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];   // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根据k值升序排列
            return b[0] - a[0];   //b - a 是降序排列，在a[0] != b[0]，的状况会根据h值降序排列
        });

        LinkedList<int[]> que = new LinkedList<>();

        for (int[] p : people) {
            //按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点
            que.add(p[1],p);   //Linkedlist.add(index, value)，会将value插入到指定index裡。
        }

        return que.toArray(new int[people.length][]);
    }
}

4.3 重难点

• 为什么按照k为下标重新插入队列就可以了？
  因为按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
• 使用LinkedList的效率更高，因为这里频繁使用插入操作，LinkedList的底层是链表，所以插入操作的性能远高于ArrayList