N车排队加油最大等待时间求解及Java代码空间复杂度优化咨询

问题规则 #

• N辆汽车排队等待加油，加油站共设x、y、z 3台燃油加油机，加油机标号优先级x > y > z
• 车辆行驶至队首时，优先选择未被占用、剩余储油量满足加油需求、标号最小的加油机加油
• 若所有空闲加油机剩余储油量都低于当前车辆加油需求，车辆必须等待
• 加注1升燃油耗时1秒，需要计算所有车辆中的最长等待时间

参考算例 #

输入：车辆加油需求数组A = [2,8,4,3,2]，加油机初始储油量x=7、y=11、z=3
输出：最长等待时间为8秒，对应各车等待时间数组[0,0,2,2,8]

推理过程 #

设w为车辆等待时长
A[0] = 2：分配到x，w=0；加油后x剩余储油量7-2=5，x需2秒完成加油
A[1] = 8：分配到y，w=0；加油后y剩余储油量11-8=3，y需8秒完成加油
A[2] = 4：z仅存3升不满足需求，等待至x空闲（等待2秒），w=2；加油后x剩余储油量5-4=1，x需4秒完成加油
A[3] = 3：x仅存1升不满足需求，分配到空闲的z（z存3升刚好满足），w=2；加油后z剩余储油量3-3=0，z需3秒完成加油
A[4] = 2：x、z剩余储油量不足，y处于占用状态，持续等待至有符合要求的加油机空闲，累计等待8秒

原有实现问题 #

• 空间冗余：自定义Car类，额外创建resolvedCars、carStack、类型转换临时列表等，空间复杂度为O(N)，随车辆数增长内存开销线性上升
• 代码bug：Pump类构造函数中car = car为局部参数赋值，未给实例属性this.car赋值，会导致加油机绑定车辆的逻辑失效
• 无效操作：批量遍历所有排队车辆累加等待时间、使用Stream做统计和类型转换，产生不必要的遍历和临时对象开销
• 冗余存储：维护已完成加油的车辆列表，计算最长等待时间不需要留存历史车辆数据

优化方案 #

优化思路 #

1. 移除所有和车辆数量绑定的对象、集合存储，仅用固定长度的数组维护3台加油机的状态（剩余储油量、当前加油剩余时长）
2. 用单个变量记录全局时间戳，遍历车辆时直接计算当前车辆等待时间，仅维护最大等待时间变量，不需要存储所有车辆的等待时长
3. 保留原有批量时间跳转逻辑（直接快进到下一个加油机空闲节点，避免逐秒遍历），去掉冗余的Stream操作和无效遍历
4. 修复原有构造函数的赋值bug
5. 最终空间复杂度降为O(1)：仅使用固定数量的变量，内存开销和输入车辆规模无关

优化后代码 #

public class GasStationSolution {
    public static void main(String[] args) {
        int[] arr = {2, 8, 4, 3, 2};
        GasStationSolution solution = new GasStationSolution();
        System.out.println("Max waiting time: " + solution.solution(arr, 7, 11, 3));
    }

    public int solution(int[] arr, int x, int y, int z) {
        // 加油机状态数组，索引0/1/2分别对应x/y/z，保证优先级顺序，每个元素存[剩余储油量, 当前加油剩余时长]
        int[][] pumps = new int[][]{
                {x, 0},
                {y, 0},
                {z, 0}
        };
        int currentTime = 0;
        int maxWaitTime = 0;

        for (int fuelRequired : arr) {
            while (true) {
                int selected = -1;
                // 按优先级顺序查找空闲且油量足够的加油机
                for (int i = 0; i < 3; i++) {
                    if (pumps[i][1] == 0 && pumps[i][0] >= fuelRequired) {
                        selected = i;
                        break;
                    }
                }

                if (selected != -1) {
                    // 成功分配加油机，更新最大等待时间
                    if (currentTime > maxWaitTime) {
                        maxWaitTime = currentTime;
                    }
                    // 更新加油机状态：扣减储油量，设置加油时长
                    pumps[selected][0] -= fuelRequired;
                    pumps[selected][1] = fuelRequired;
                    break;
                }

                // 无可用加油机，快进到最近一个加油机空闲的时间点
                int minRemainTime = Integer.MAX_VALUE;
                for (int[] pump : pumps) {
                    if (pump[1] > 0 && pump[1] < minRemainTime) {
                        minRemainTime = pump[1];
                    }
                }
                // 推进全局时间，更新所有加油机的剩余加油时长
                for (int[] pump : pumps) {
                    if (pump[1] > 0) {
                        pump[1] -= minRemainTime;
                    }
                }
                currentTime += minRemainTime;
            }
        }
        return maxWaitTime;
    }
}

内容的提问来源于stack exchange，提问作者Sandeep Das