代码随想录day29 | leetcode 134.加油站 135.分发糖果 860.柠檬水找零 406.根据身高重建队列

134.加油站

思路

如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

Java

class Solution {
    public int jump(int[] nums) {
        int jumps = 0; // 跳跃次数
        int curEnd = 0; // 当前跳跃覆盖的最远位置
        int nextMax = 0; // 下一次跳跃覆盖的最远位置

        for (int i = 0; i < nums.length - 1; i++) {
            nextMax = Math.max(nextMax, i + nums[i]); // 更新下一次的最远位置

            if (i == curEnd) { // 当前跳跃到达了覆盖范围的末尾
                jumps++; // 增加跳跃次数
                curEnd = nextMax; // 更新当前覆盖范围
                if (curEnd >= nums.length - 1) { // 如果已经可以到达终点，提前结束
                    break;
                }
            }
        }
        return jumps;
    }
}

关键逻辑

curSum 重置：
- 当 curSum < 0 时，说明从当前起点到当前站点之间的油量不足以到达下一站。
- 此时假设下一站为新的起点，并将 curSum 重置为 0。
- 因为问题保证至少有一个解，所以继续累加判断新的起点即可。
totalSum 判断：
- 如果整个环路的总净油量（totalSum）小于 0，则无论从哪里开始，油量都不足以完成一圈。

135.分发糖果

思路

这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
先确定右边评分大于左边的情况（也就是从前向后遍历）
再确定左孩子大于右孩子的情况（从后向前遍历）

Java

class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candyVec = new int[len];
        int result = 0;

        // 初始化，每个人至少有一个糖果
        for (int i = 0; i < len; i++) {
            candyVec[i] = 1;
        }

        // 从左往右遍历
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            }
        }

        // 从右往左遍历，同时计算结果
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }

        // 累加所有糖果
        for (int candy : candyVec) {
            result += candy;
        }

        return result;
    }
}

关键逻辑解析

左遍历规则：
- 如果当前学生的评分比左边的高，则糖果数应该比左边多 1。
- 遍历后，保证每个学生的糖果满足“比左边评分高”的条件。
右遍历规则：
- 如果当前学生的评分比右边高，则糖果数应该比右边多 1。
- 同时取当前糖果数和（右侧糖果数 + 1）的较大值，确保满足两侧评分的规则。

860.柠檬水找零

思路

只需要维护三种金额的数量，5，10和20。
有如下三种情况：
情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个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++;
            } else if (bills[i] == 10) {
                five--;
                ten++;
            } else if (bills[i] == 20) {
                if (ten > 0) {
                    ten--;
                    five--;
                } else {
                    five -= 3;
                }
            }
            if (five < 0 || ten < 0) return false;
        }
        
        return true;
    }
}

总结

咋眼一看好像很复杂，分析清楚之后，会发现逻辑其实非常固定。
这道题目可以告诉大家，遇到感觉没有思路的题目，可以静下心来把能遇到的情况分析一下，只要分析到具体情况了，一下子就豁然开朗了。
如果一直陷入想从整体上寻找找零方案，就会把自己陷进去，各种情况一交叉，只会越想越复杂了。

406.根据身高重建队列

思路

与135. 分发糖果类似,遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

Java

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 身高从大到小排（身高相同k小的站前面）
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];   //如果身高相同，按 k 值升序排列
            return b[0] - a[0];   //如果身高不同，按身高降序排列
        });
        LinkedList<int[]> que = new LinkedList<>();
        for (int[] p : people) {
            que.add(p[1],p);   //将当前元素插入到索引为 p[1] 的位置
        }
        return que.toArray(new int[people.length][]);
    }
}

Lambda 表达式的作用

Lambda 表达式的格式是：

(parameters) -> expression 或 { statements }

它的作用是简化匿名类的写法，用来快速定义函数式接口的实现。对于 Comparator 接口，Lambda 表达式替代了传统的匿名类来定义排序规则。

Lambda 表达式在 `Arrays.sort` 中的使用

Arrays.sort(people, (a, b) -> { ... }) 是对二维数组 people 进行排序。

a 和 b 是 people 数组中的两个元素（在这里每个元素是一个长度为 2 的数组）。
Comparator 接口通过 compare(T o1, T o2) 定义排序规则，这里的 a 和 b 就是 o1 和 o2。

代码中的逻辑

Arrays.sort(people, (a, b) -> {
    if (a[0] == b[0]) return a[1] - b[1];   // 身高相同时，按 k 值升序排列
    return b[0] - a[0];   // 身高不同，按身高降序排列
});

1. 如果身高相同 (`a[0] == b[0]`)：

return a[1] - b[1];

比较 a[1] 和 b[1] 的大小。
a[1] - b[1] > 0 时，b 会排在 a 前面（升序排列）。
简单理解就是 k 值越小的排在前面。

2. 如果身高不同 (`a[0] != b[0]`)：

return b[0] - a[0];

比较 b[0] 和 a[0] 的大小。
b[0] - a[0] > 0 时，a 会排在 b 前面（降序排列）。
简单理解就是 身高越高的排在前面。

Lambda 表达式的展开形式

用传统匿名类实现同样功能：

Arrays.sort(people, new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
        if (a[0] == b[0]) {
            return a[1] - b[1];
        }
        return b[0] - a[0];
    }
});

可以看到，Lambda 表达式 (a, b) -> {...} 简化了匿名类的写法。

总结

Lambda 表达式语法：
- (a, b) -> 表达式
- (a, b) -> { 代码块 }
本例中：
- a 和 b 是二维数组 people 中的两个元素。
- a[0] 和 b[0] 是身高，a[1] 和 b[1] 是 k 值。
- 排序规则：- 先按身高降序排列。
  - 若身高相同，按 k 值升序排列。