难度: Hard
Submission
运行时间: 74 ms
内存: 34.0 MB
class Solution:
def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
n=len(arrival)
ans=[0]*n
t,door=0,1#时间 门状态
#进门队员游标 出门队员游标
et,lf=0,0
while et < n or lf < n:
#如果 两个游标最小的到达时间都大于 t
#把t移动到最小值 门重置到离开优先
if arrival[min(et,lf)]>t:
door=1
t=arrival[min(et,lf)]
#判断门状态
if door==1:
#还有离开的人 切离开的人时间小于 t
#移动游标直到不能离开
if lf<n and arrival[lf]<=t:
while lf <n and arrival[lf]<=t:
if state[lf]==1:
ans[lf]=t
t+=1
lf+=1
#没有改变门状态
else:door=0
continue
if door==0:
#同上
if et<n and arrival[et]<=t:
while et<n and arrival[et]<=t:
if state[et]==0:
ans[et]=t
t+=1
et+=1
else:door=1
continue
return ans
Explain
这段代码用于模拟人们按照给定的到达时间和状态（进门或离开）通过一扇门的过程。数组 'arrival' 包含每个人的到达时间，数组 'state' 包示每个人是进门还是出门（0为进门，1为离开）。解法使用了两个指针 'et' 和 'lf' 分别跟踪需要进门和离开的人的索引。变量 't' 记录当前时间，而 'door' 记录门的状态（0为关闭，1为开启）。整个模拟过程中，按照时间顺序处理进门和出门事件，确保每个人在适当的时间通过门。如果当前时间没有人通过门，则时间跳跃到下一个人到达的时间。如果门处于开启状态，首先处理所有可以离开的人，然后转换到进门状态；如果门处于关闭状态，则首先处理所有可以进门的人，然后转换到离开状态。通过这种方式，模拟直到所有人都处理完毕。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
n = len(arrival)
ans = [0] * n
t, door = 0, 1 # 当前时间和门状态（1表示开启）
et, lf = 0, 0 # 进门的指针和离开的指针
while et < n or lf < n:
if arrival[min(et,lf)] > t:
door = 1 # 重置门状态为开启
t = arrival[min(et, lf)] # 跳转到下一个事件时间
if door == 1:
if lf < n and arrival[lf] <= t:
while lf < n and arrival[lf] <= t:
if state[lf] == 1:
ans[lf] = t # 更新离开时间
t += 1 # 时间前进
lf += 1 # 移动离开指针
else:
door = 0 # 更改门状态为关闭
if door == 0:
if et < n and arrival[et] <= t:
while et < n and arrival[et] <= t:
if state[et] == 0:
ans[et] = t # 更新进门时间
t += 1 # 时间前进
et += 1 # 移动进门指针
else:
door = 1 # 更改门状态为开启
return ans
Explore
使用两个不同的指针 'et' 和 'lf' 是为了能够独立追踪进门和离开的人。这种方法允许算法在不需要额外排序或筛选步骤的情况下，有效地处理两种不同类型的事件（进门和离开）。每个指针独立地遍历 'arrival' 数组，根据 'state' 数组的值分别处理进门和离开的事件，从而使得代码更加简洁和高效。
在代码中，如果同时有人需要进门和离开，处理方式依赖于当前门的状态（由 'door' 变量表示）。如果门处于开启状态（'door == 1'），代码首先处理所有到达时间小于等于当前时间 't' 且需要离开的人（'state[lf] == 1'），之后再处理需要进门的人。如果没有更多需要离开的人，或者他们的到达时间大于当前时间，门的状态会转换为关闭（'door = 0'），然后处理进门的人。这样的处理顺序确保了在同一时间点，离开的操作会优先于进门的操作，遵循逻辑上的先出后进原则。
在循环中检查 'arrival[lf] <= t' 和 'arrival[et] <= t' 的条件是为了确保只有在人物到达时间小于等于当前时间 't' 时，该人物才能通过门。这个条件防止了在人物实际到达之前错误地处理他们的进门或离开事件。这是基于现实世界中的常识：一个人只能在到达门口后才能决定进门或离开。因此，这些条件确保了事件的处理与人物的到达时间同步进行，避免了时间逻辑上的错误。