有一座山，有一条受欢迎的远足小径。在步道的某个地方，路径会变窄，因此一次只能有一个徒步旅行者通过。当多名徒步旅行者同时到达此点时，可以建立两个队列，一个供徒步旅行者上山，一个供徒步旅行者下山。每个徒步旅行者需要一秒钟才能完全穿过小路的狭窄部分。如果所有等待的徒步旅行者都朝同一方向前进（上升或下降），那么他们可以立即开始按照到达的顺序一次穿过一个。当双向徒步旅行者步行时，当地习俗规定了以下程序来确定哪个徒步旅行者有优先权并可以通过路径。海关如下：
如果前一秒没有徒步旅行者经过，那么第一个等待下山的徒步旅行者先走
如果在前一秒，有一个下降的徒步旅行者经过，那么第一个下降的徒步旅行者先走
如果前一秒有登山者经过，则上升队列中的登山者先走
对于每个徒步旅行者，找出他们穿过步道狭窄部分的时间。
功能说明
完成函数getResult
getResult 有以下参数：
intarrival[n] 一个整数数组，其中索引值是徒步旅行者到达步道狭窄部分的时间（以秒为单位）。如果到达 [i] = 到达[j] 并且 i < j then then hiker i arrives before hiker j.
int Direction：一个整数数组，其中索引处的值是徒步旅行者的方向：0 表示上升，1 表示下降
退货：
一个整数数组，其中索引 i 处的值是第 i 个徒步旅行者穿过步道狭窄部分的时间
这是我写的代码。它适用于第一个测试用例。然而，对于第二个测试用例，它是错误的。
def getResult(arrival, direction):
n = len(arrival)
result = [0] * n
last_direction = -1 # -1 represents no hiker passed through in the previous second
i = 0
while i < len(arrival):
ascending_queue = []
descending_queue = []
if i == 0:
if direction[0] == 0:
#ascending_queue.pop(0)
result[0] = arrival[0]
last_direction = 0
else:
#descending_queue.pop(0)
result[0] = arrival[0]
last_direction = 1
a = i + 1 if i == 0 else i
chk = False
while(a + 1 < len(arrival) and arrival[a] == arrival[a+1]):
if direction[a] == 0:
ascending_queue.append(a)
else:
descending_queue.append(a)
if direction[a+1] == 0:
ascending_queue.append(a+1)
else:
descending_queue.append(a+1)
a += 1
chk = True
if ascending_queue and descending_queue:
if last_direction == 0:
next_val = i
idx = ascending_queue.pop(0)
result[idx] = arrival[i + 1]
prev = result[idx]
next_val = max(next_val,idx)
while ascending_queue:
idx = ascending_queue.pop(0)
result[idx] = prev + 1
last_direction = direction[idx]
prev = result[idx]
next_val = max(next_val,idx)
while descending_queue:
idx = descending_queue.pop(0)
result[idx] = prev + 1
last_direction = direction[idx]
prev = result[idx]
next_val = max(next_val,idx)
i = next_val
else:
next_val = i
idx = descending_queue.pop(0)
result[idx] = arrival[i + 1]
prev = result[idx]
next_val = max(next_val,idx)
while descending_queue:
idx = descending_queue.pop(0)
result[idx] = prev + 1
last_direction = direction[idx]
prev = result[idx]
next_val = max(next_val,idx)
while ascending_queue:
idx = ascending_queue.pop(0)
result[idx] = prev + 1
last_direction = direction[idx]
prev = result[idx]
next_val = max(next_val,idx)
i = next_val
else:
if chk:
j = i
while(arrival[j] == arrival[j+1]):
result[j] = arrival[i] if j == i else result[j-1] + 1
j += 1
else:
result[i] = arrival[i]
last_direction = direction[i]
if chk:
i = a + 1
else:
i += 1
return result
# Example usage:
#arrival = [0, 1, 1, 3, 3]
#direction = [0, 1, 0, 0, 1]
# Output: [0, 2, 1, 4, 3]
arrival = [0, 0, 1, 4]
direction = [0, 1, 1, 0]
#Ouput = [2, 0, 1, 4]
对于第二个测试用例，我的代码返回 [0, 0, 1, 4]。我的方法的第一个缺点是我只添加同时到达的徒步旅行者，但在第二种情况下，当我们按降序处理索引 1 处的徒步旅行者时，我们必须按降序处理索引 2 处的徒步旅行者，但我的方法将首先处理索引 0 处的徒步旅行者。无法想出不同的方法来做到这一点。谢谢
对任何不同/新的方法/语言（Java/C++）或对此方法的修改持开放态度。 谢谢
两个队列的想法很好，但我会把所有徒步旅行者放在这些队列中，然后随着时间的流逝从队列中弹出。我还将徒步旅行者 ID（输入列表中的索引）与其到达时间合并在一个元组中。
我建议这样做：
def getResult(arrival, direction):
# It is assumed the arrival list has its time stamps in non-decreasing order
# Determine a time before which all hikers will have gone through the narrow pass
maxtime = arrival[-1] + len(arrival)
def makeQueue(filter_dir):
q = [(hiker, time)
for hiker, (time, desc) in enumerate(zip(arrival, direction))
if desc == filter_dir]
q.append((-1, maxtime)) # Add a dummy entry to avoid empty queue issues
return q[::-1] # Reverse so we can pop from the queue in the right order
# Put all hikers in one of the two queues, with their id and time of arrival
queues = [makeQueue(0), makeQueue(1)] # Ascending hikers, descending hikers
result = [0] * len(arrival)
currentTime = 0
# As long there are hikers that didn't pass through yet
while len(queues[0]) + len(queues[1]) > 2: # (NB: each queue has a dummy at index 0)
# Get the earliest time a hiker arrived or will arrive at the narrow pass
currentTime = max(currentTime, min(queues[0][-1][1], queues[1][-1][1]))
# If descending hikers are waiting at the narrow pass, they have priority
activeQueue = queues[queues[1][-1][1] <= currentTime]
# Let all waiting people on the selected side go through the narrow pass.
while activeQueue[-1][1] <= currentTime: # Someone waiting?
result[activeQueue.pop()[0]] = currentTime # One hiker walks through
currentTime += 1 # One second passes...
# All hikers went through the narrow pass
return result