2026-11-12：交通灯的最大等待时间。用go语言，有一个固定的循环周期 period。数组 lights 中第 i 个元素表示第 i 个路口的绿灯持续时间。所有路口在时刻 0 同时进入绿灯，并按

2026-11-12：交通灯的最大等待时间。用go语言，有一个固定的循环周期 period。数组 lights 中第 i 个元素表示第 i 个路口的绿灯持续时间。所有路口在时刻 0 同时进入绿灯，并按 period 秒为一个周期反复循环；因此第 i 个路口的红灯持续时间是 period 减去 lights[i]。

另有数组 arrivalTime，其中每个元素表示一辆车到达的时间。每辆车都必须选择一个路口通过，多个路口分配规则允许同一路口服务任意多辆车；只要该路口当时是绿灯，车辆可以同时通过，不会互相排队或耽搁。

若某辆车在时刻 arrivalTime[j] 到达，并被安排到第 i 个路口，则先计算 r = arrivalTime[j] 对 period 取余。如果 r 小于 lights[i]，这辆车无需等待；否则它要等到本周期结束，等待时间为 period - r。

一种分配方式的总代价定义为：所有车辆等待时间中的最大值。目标是给每辆车选择合适的路口，使这个最大等待时间尽可能小，并返回该最小值。

2 <= period <= 1000000000。

1 <= lights.length <= 10000。

1 <= lights[i] <= period - 1。

1 <= arrivalTime.length <= 100000。

1 <= arrivalTime[i] <= 1000000000。

输入： period = 8, lights = [2,3], arrivalTime = [2,5,8,11]。

输出： 5。

解释：

一种最优方案如下：

将 arrivalTime[0] 分配给满足 lights[1] = 3 的交通信号灯。此时，r = 2 % 8 = 2。由于 2 < 3，等待时间为 0。

将 arrivalTime[1] 分配给满足 lights[0] = 2 的交通信号灯。此时，r = 5 % 8 = 5。由于 5 >= 2，等待时间为 8 - 5 = 3。

将 arrivalTime[2] 分配给满足 lights[0] = 2 的交通信号灯。此时，r = 8 % 8 = 0。由于 0 < 2，等待时间为 0。

将 arrivalTime[3] 分配给满足 lights[0] = 2 的交通信号灯。此时，r = 11 % 8 = 3。由于 3 >= 2，等待时间为 8 - 3 = 5。

该分配方案的惩罚值为 5，这是可能得到的最小值。也可能存在其他最优分配方案。

题目来自力扣4025。

大体过程如下：

1. 理解红绿灯规则
   对任意到达时间，先对固定周期 period 取余，得到该车在当前周期内的位置 r。
   对第 i 个路口：

   • 如果 r < lights[i]，说明该路口当前是绿灯，车辆可以直接通过，等待时间为 0；
   • 如果 r >= lights[i]，说明该路口当前是红灯，车辆需要等到本周期结束，等待时间为 period - r。

2. 抓住关键观察：只需要知道最大的绿灯持续时间
   令 mx 为 lights 数组中的最大值，也就是所有路口中绿灯持续时间最长的那个路口的绿灯时长。
   对一辆车取余后的到达位置 r：

   • 如果 r < mx，那么最大绿灯时长的那个路口当前一定是绿灯，因此这辆车可以被安排到该路口，等待时间为 0；
   • 如果 r >= mx，由于 mx 已经是所有 lights[i] 中的最大值，所以 r 一定不小于任何一个路口的绿灯时长。也就是说，此时所有路口都是红灯，无论选择哪个路口，车辆都必须等待到本周期结束，等待时间为 period - r。

   因为题目允许同一个路口同时服务任意多辆车，所以所有 r < mx 的车都可以安排到最大绿灯时长的那个路口，不会互相排队，也不会产生等待。

3. 确定全局最大等待时间
   总代价是所有车辆等待时间中的最大值。

   • 对于 r < mx 的车辆，可以做到等待时间为 0，不会影响最大值；
   • 对于 r >= mx 的车辆，所有路口都红灯，等待时间固定为 period - r，无法通过选择其他路口来减少。

   因此，只需要在所有“无法零等待”的车辆中，找出最大的 period - r，它就是最终的最小可能最大等待时间。如果所有车辆都能零等待，则答案为 0。

4. 代码执行流程

   • 先通过 slices.Max(lights) 求出所有绿灯持续时间的最大值 mx。
   • 初始化答案 ans 为 0，表示当前记录的最大等待时间。
   • 遍历每一个到达时间：
     • 对 period 取余，得到该车在当前周期内的位置 r；
     • 如果 r >= mx，说明所有路口都是红灯，该车必须等待 period - r；
     • 用这个等待时间更新 ans，即取当前最大值；
     • 如果 r < mx，说明存在绿灯路口，可以零等待通过，不需要更新答案。
   • 遍历结束后，ans 就是所有不可避免等待中的最大值，也就是题目要求的最小可能最大等待时间。

5. 结合示例说明
   输入为 period = 8，lights = [2, 3]，所以 mx = 3。
   到达时间依次为：

   • 2：2 % 8 = 2 < 3，可零等待，等待 0；
   • 5：5 % 8 = 5 >= 3，所有路口红灯，等待 8 - 5 = 3，当前最大等待为 3；
   • 8：8 % 8 = 0 < 3，可零等待，等待 0；
   • 11：11 % 8 = 3 >= 3，所有路口红灯，等待 8 - 3 = 5，当前最大等待更新为 5。
     因此最终答案为 5。

6. 正确性要点
   对于任意一辆 r >= mx 的车，所有路口都红灯，所以它至少需要等待 period - r，任何分配方式都无法降低这个等待时间；而所有 r < mx 的车都可以安排到最大绿灯时长的路口实现零等待。因此，最终最大等待时间恰好等于所有不可避免等待车辆中的最大等待时间，这个值既不可低于，也可以达到。

时间复杂度：设 lights 长度为 n，arrivalTime 长度为 m。求最大值需要扫描 lights，遍历到达时间需要扫描 arrivalTime，所以总时间复杂度为 O(n + m)。
额外空间复杂度：只使用了常数个变量，不需要与输入规模相关的额外空间，因此总额外空间复杂度为 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

func minPenalty(period int, lights []int, arrivalTime []int) (ans int) {
	mx := slices.Max(lights)
	for _, t := range arrivalTime {
		t %= period
		if t >= mx {
			ans = max(ans, period-t)
		}
	}
	return
}

func main() {
	period := 8
	lights := []int{2, 3}
	arrivalTime := []int{2, 5, 8, 11}

	result := minPenalty(period, lights, arrivalTime)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def minPenalty(period, lights, arrivalTime):
    mx = max(lights)
    ans = 0

    for t in arrivalTime:
        t %= period
        if t >= mx:
            ans = max(ans, period - t)

    return ans


def main():
    period = 8
    lights = [2, 3]
    arrivalTime = [2, 5, 8, 11]

    result = minPenalty(period, lights, arrivalTime)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

int minPenalty(int period, const std::vector<int>& lights, const std::vector<int>& arrivalTime) {
    int mx = *std::max_element(lights.begin(), lights.end());
    int ans = 0;

    for (int t : arrivalTime) {
        t %= period;
        if (t >= mx) {
            ans = std::max(ans, period - t);
        }
    }

    return ans;
}

int main() {
    int period = 8;
    std::vector<int> lights = {2, 3};
    std::vector<int> arrivalTime = {2, 5, 8, 11};

    int result = minPenalty(period, lights, arrivalTime);
    std::cout << result << std::endl;

    return 0;
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/weixin_48502062/article/details/170562686