What is the key insight for the Minimum Number of Chairs in a Waiting Room problem?

The key insight is tracking the running count of people and recording the peak occupancy using a simple string iteration.

Can this problem be solved with additional data structures?

Yes, but using counters is optimal; extra structures like arrays or queues are unnecessary and increase space complexity.

What should I do if an 'L' appears before any 'E'?

Ensure the sequence is valid; the problem guarantees valid sequences, so the counter should not go negative in correct input.

Does the solution pattern relate to other problems?

Yes, it matches the string plus simulation pattern where tracking state changes over time is critical.

How do I know the peak number of people is the correct chair count?

Because the peak occupancy represents the maximum number of people simultaneously present, which equals the minimum chairs needed.

#3168

Easy

auto_awesomestring·结合·模拟

LeetCode 题解工作台

候诊室中的最少椅子数

给你一个字符串 s ，模拟每秒钟的事件 i ：如果 s[i] == 'E' ，表示有一位顾客进入候诊室并占用一把椅子。如果 s[i] == 'L' ，表示有一位顾客离开候诊室，从而释放一把椅子。返回保证每位进入候诊室的顾客都能有椅子坐的最少椅子数，假设候诊室最初是空的。示例 1：输…

字符串模拟

题目描述

给你一个字符串 s，模拟每秒钟的事件 i：

如果 s[i] == 'E'，表示有一位顾客进入候诊室并占用一把椅子。
如果 s[i] == 'L'，表示有一位顾客离开候诊室，从而释放一把椅子。

返回保证每位进入候诊室的顾客都能有椅子坐的最少椅子数，假设候诊室最初是空的。

示例 1：

输入：s = "EEEEEEE"

输出：7

解释：

每秒后都有一个顾客进入候诊室，没有人离开。因此，至少需要 7 把椅子。

示例 2：

输入：s = "ELELEEL"

输出：2

解释：

假设候诊室里有 2 把椅子。下表显示了每秒钟等候室的状态。

秒	事件	候诊室的人数	可用的椅子数
0	Enter	1	1
1	Leave	0	2
2	Enter	1	1
3	Leave	0	2
4	Enter	1	1
5	Enter	2	0
6	Leave	1	1

示例 3：

输入：s = "ELEELEELLL"

输出：3

解释：

假设候诊室里有 3 把椅子。下表显示了每秒钟等候室的状态。

秒	事件	候诊室的人数	可用的椅子数
0	Enter	1	2
1	Leave	0	3
2	Enter	1	2
3	Enter	2	1
4	Leave	1	2
5	Enter	2	1
6	Enter	3	0
7	Leave	2	1
8	Leave	1	2
9	Leave	0	3

提示：

1 <= s.length <= 50
s 仅由字母 'E' 和 'L' 组成。
s 表示一个有效的进出序列。

lightbulb

解题思路

方法一：模拟

我们用变量 $\textit{cnt}$ 来记录当前需要的椅子数，用变量 $\textit{left}$ 来记录当前剩余的空椅子数。遍历字符串 $\textit{s}$ ，如果当前字符是 'E'，那么如果有剩余的空椅子，就直接使用一个空椅子，否则需要增加一个椅子；如果当前字符是 'L'，那么剩余的空椅子数加一。

遍历结束后，返回 $\textit{cnt}$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $\textit{s}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minimumChairs(self, s: str) -> int:
        cnt = left = 0
        for c in s:
            if c == "E":
                if left:
                    left -= 1
                else:
                    cnt += 1
            else:
                left += 1
        return cnt

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is processed once. Space complexity is O(1) as only counters are stored, independent of string length.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a simple one-pass solution instead of multiple simulations.
question_mark
Confirm the candidate correctly handles sequences where exits occur before entries.
question_mark
Check understanding of peak tracking as the critical metric for chair count.

warning

常见陷阱

外企场景

error
Failing to decrement the counter correctly when processing 'L'.
error
Using extra data structures unnecessarily, increasing space usage.
error
Not updating the maximum occupancy at each step, leading to incorrect chair count.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute minimum chairs if multiple rooms are allowed and people can move between them.
arrow_right_alt
Determine the waiting room occupancy over time as a list instead of just peak value.
arrow_right_alt
Handle cases where the string may contain invalid sequences and raise an error.

help

常见问题

外企场景

继续练习

#3174 清除数字 #3248 矩阵中的蛇 #3271 哈希分割字符串