体育场闸门安保值守判断代码挑战：现有Python解法输出异常

有26个以大写英文字母A到Z编号的闸门。每个闸门会在第一位客人进入前打开，在最后一位应从此闸门进入的客人到达后立即关闭。客人无法同时进入体育场。每个闸门需指派一名保安值守才能完成合规检查，体育场共有k名保安。若同时打开的闸门数量超过k，将存在无人值守的闸门（保安在负责的闸门关闭前不得离岗）。需判断是否存在某一时刻打开的闸门数量超过k？已知持票客人的进入顺序。

输入输出示例 #

输入1 #

• 人数 = 5
• 保安数量(k) = 1
• 客人使用的闸门顺序：AABBB
  输出：NO

输入2 #

• 人数 = 5
• 保安数量(k) = 1
• 客人使用的闸门顺序：ABABB
  输出：YES

我的尝试 #

我尝试用deque存储进入的闸门字母，当遇到与前一个不同的字母时，弹出元素直到遇到重复字母，但无法得到预期输出。以下是我编写的代码：

from collections import deque
def solve(people, k, gate):
    stack = deque()  # 跟踪已打开的闸门
    counter = 0  # 已打开闸门的计数器
    for gate in gate_usage:
        if len(stack) == 0 or stack[-1] == gate:
            stack.append(gate)
        else:
            while len(stack) > 0 and stack[-1] != gate:
                stack.pop()
                counter += 1
                if counter > k:
                    return "NO"
    return "YES"


no_of_people = 5
k = 1
gate_usage = "ABABB"

print(solve(no_of_people, k, gate_usage))

问题分析与正确解法 #

你的代码逻辑存在核心问题：计数器的使用和闸门关闭时机的判断完全错误，没法准确追踪当前同时打开的闸门数量。

正确思路 #

1. 先记录每个闸门最后一次出现的位置，精准确定闸门的关闭时机。
2. 遍历客人的闸门顺序，维护一个当前打开的闸门集合。
3. 遇到未打开的闸门就加入集合，立刻检查集合大小是否超过k——如果超过，直接返回"YES"。
4. 当遍历到闸门最后一次出现的位置时，把它从集合中移除（闸门关闭）。

正确代码 #

def solve(people, k, gate_usage):
    # 记录每个闸门最后一次出现的索引
    last_occurrence = {}
    for idx, gate in enumerate(gate_usage):
        last_occurrence[gate] = idx
    
    opened_gates = set()
    for idx, gate in enumerate(gate_usage):
        # 闸门未打开，加入集合
        if gate not in opened_gates:
            opened_gates.add(gate)
            # 检查当前打开数量是否超标
            if len(opened_gates) > k:
                return "YES"
        # 当前是闸门最后一次使用，关闭它
        if idx == last_occurrence[gate]:
            opened_gates.remove(gate)
    # 全程未超标
    return "NO"

# 测试示例1
no_of_people = 5
k = 1
gate_usage = "AABBB"
print(solve(no_of_people, k, gate_usage))  # 输出NO

# 测试示例2
no_of_people = 5
k = 1
gate_usage = "ABABB"
print(solve(no_of_people, k, gate_usage))  # 输出YES

代码说明 #

• 预处理最后出现位置：一次遍历就能记录每个闸门的关闭时机，避免后续重复判断。
• 实时检查闸门数量：每次新增打开的闸门时立刻检查数量，一旦超过k就直接返回结果，无需遍历剩余内容。
• 及时关闭闸门：当客人是该闸门最后一位使用者时，立即从打开集合中移除，保证集合始终代表当前同时打开的闸门。

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