算法训练营day30 | {134.加油站, 135.分发糖果, 860.柠檬水找零, 406.根据身高重建队列}

第八章贪心算法part03，遇到两个维度同时要比较的题目，必须先确定一边，再确定另一边。

134. 加油站

1.1 解题分析

暴力解法，先计算每个站点的净收益，然后枚举起点，从该起点出发绕一圈，油量不为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] profit = new int[gas.length];

        for (int i = 0; i < profit.length; i++) {
            profit[i] = gas[i] - cost[i];
        }

        for (int i = 0; i < profit.length; i++) { // 枚举起点
            int sum = 0;
            int j = i;
            for (; j < i + profit.length; j++) {
                sum += profit[j % profit.length];
                if (sum < 0) break;
            }
            if (j == i + profit.length) return i;
        }
        return -1;
    }
}
  • 换一种思路，首先如果总油量减去总消耗>=0那么一定是可以跑完一圈的。
  • 其次，这题贪心在哪里？如果从i出发，在j位置油量变成负数，那么i~j之间的任意一个点，都不可能成为起点。
  • 为什么？假设从i到j的累计和是负数
    1
    profit[i] + profit[i+1] + ... + profit[j] < 0
    那你如果从i+1、i+2出发，只会更少油，更不可能成功。所以一旦失败，可以跳过一段区间。 只用遍历一遍数组，时间复杂度降低为O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;  // 总收益
        int cur = 0;  // 当前油箱
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            cur += diff;

            if (cur < 0) {
                start = i + 1;
                cur = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
}

135. 分发糖果

2.1 解题分析

题目要求：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中，评分高的孩子必须获得更多的糖果。

但这道题如果两边一起考虑一定会顾此失彼，必须要确定一边之后，再确定另一边。明确解题的顺序。

例如先确定右边评分大于左边的情况（从前往后遍历）。此时局部最优，只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。局部最优可以推出全局最优。再确定左边大于右边的情况（从后往前遍历），类似的贪心分析方法，不过此时要保证第i个孩子的糖果数量既比大于左边孩子的，又大于右边孩子的，要取最值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int candy(int[] ratings) {
        int[] candy = new int[ratings.length];
        Arrays.fill(candy, 1);
        // 1. 右边的孩子比左边孩子糖果多
        for (int i = 1; i < candy.length; i++) {
            if (ratings[i] > ratings[i - 1]) candy[i] = candy[i - 1] + 1;
        }
        // 2. 左边的孩子比右边孩子糖果多
        for (int i = candy.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
        int result = 0;
        for (int c : candy) {
            result += c;
        }
        return result;
    }
}

860. 柠檬水找零

3.1 解题分析

题目要求在每一步，都能正确找零，保证是合法的；贪心的关键是优先用10元找零，因为5元是万能货币，10元只能给20元找零。并且只能事前决策，不能事后补救。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for (int bill : bills) {
            if (bill == 5) five++;
            else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            }
            else {
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

406. 根据身高重建队列

4.1 解题分析

这题的难点不在想贪心怎么落地，在于Java API，比如二维数组排序、ArrayList怎么转为二维数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2)-> {
            if (o1[0] != o2[0]) {
                return o2[0] - o1[0];
            }
            return o1[1] - o2[1];
        });

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

        int[][] result = new int[people.length][2];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

5. JAVA API小结

  • Arrays.fill(arr, 1)：快速对数组赋初始值。
  • 数组排序，一维数组、二维数组，都可以用Arrays.sort配合自定义比较器的方式。关于比较器Comparetor的固定规则，涉及到升序还是降序：
    • 返回 < 0 : o1 比 o2 小，o1放前面
    • 返回 > 0 : o1 比 o2 大，o1放后面
  • List<int[]>转int[][]：
    1
    2
    3
    4
    int[][] result = new int[people.length][2];
    for (int i = 0; i < list.size(); i++) {
        result[i] = list.get(i);
    }
Leetcode > 贪心算法
#Java #代码随想录
算法训练营day30 | {134.加油站, 135.分发糖果, 860.柠檬水找零, 406.根据身高重建队列}
http://paopaotangzu.xyz/cn/day30_leetcode/
作者
PROTON TANG
发布于
2026年1月16日
许可协议