代码随想录day25：贪心part3

134. 加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int ans = 0;
        int minS = 0; // 最小油量
        int s = 0; // 油量
        for (int i = 0; i < gas.length; i++) {
            s += gas[i] - cost[i]; // 在 i 处加油，然后从 i 到 i+1
            if (s < minS) {
                minS = s; // 更新最小油量
                ans = i + 1; // 注意 s 减去 cost[i] 之后，汽车在 i+1 而不是 i
            }
        }
        // 循环结束后，s 即为 gas 之和减去 cost 之和
        return s < 0 ? -1 : ans;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/gas-station/solutions/2933132/yong-zhe-xian-tu-zhi-guan-li-jie-pythonj-qccr/

灵神题解  的画图解释很清晰

135. 分发糖果

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length]; // 从左到右的糖果分配数组
        int[] right = new int[ratings.length]; // 从右到左的糖果分配数组
        Arrays.fill(left, 1); // 初始化每个孩子至少分到1颗糖
        Arrays.fill(right, 1); // 初始化每个孩子至少分到1颗糖
        
        // 从左到右的遍历
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1; // 如果当前孩子的评分高于前一个孩子，则糖果比前一个孩子多1
            }
        }

        int count = left[ratings.length - 1]; // 初始糖果总数为最后一个孩子的糖果

        // 从右到左的遍历
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1; // 如果当前孩子的评分高于下一个孩子，则糖果比下一个孩子多1
            }
            count += Math.max(left[i], right[i]); // 取左右两边分配的最大值
        }

        return count; // 返回总糖果数
    }
}

K神题解同样是图解，清晰就完了

860. 柠檬水找零

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

简单自己秒

406. 根据身高重建队列

    /**
     * 解题思路：先排序再插入
     * 1.排序规则：按照先H高度降序，K个数升序排序
     * 2.遍历排序后的数组，根据K插入到K的位置上
     *
     * 核心思想：高个子先站好位，矮个子插入到K位置上，前面肯定有K个高个子，矮个子再插到前面也满足K的要求
     *
     * @param people
     * @return
     */
    public int[][] reconstructQueue(int[][] people) {
        // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
        // 再一个一个插入。
        // [7,0]
        // [7,0], [7,1]
        // [7,0], [6,1], [7,1]
        // [5,0], [7,0], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

        LinkedList<int[]> list = new LinkedList<>();
        for (int[] i : people) {
            list.add(i[1], i);
        }

        return list.toArray(new int[list.size()][2]);
    }


作者：pphdsny
链接：https://leetcode.cn/problems/queue-reconstruction-by-height/solutions/23208/406-gen-ju-shen-gao-zhong-jian-dui-lie-java-xian-p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个思路是真牛逼