Easy

题目描述

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

  • 如果 s[i] == 'E'，一个人进入候车室并坐在其中一张椅子上。
  • 如果 s[i] == 'L'，一个人离开候车室，释放一张椅子。

返回所需的最少椅子数，使得每个进入候车室的人都能有椅子坐，假设候车室最初是空的。

示例 1：

输入：s = "EEEEEEE"
输出：7
解释：
每一秒都有一个人进入候车室，没有人离开。因此，至少需要 7 张椅子。

示例 2：

输入：s = "ELELEEL"
输出：2
解释：
考虑候车室有 2 张椅子。下表显示了每一秒候车室的状态。

示例 3：

输入：s = "ELEELEELLL"
输出：3
解释：
考虑候车室有 3 张椅子。下表显示了每一秒候车室的状态。

约束条件：

  • 1 <= s.length <= 50
  • s 只包含字母 ‘E’ 和 ‘L’
  • s 代表一个有效的进入和离开序列

提示：

  • 从左到右遍历字符串，使用一个变量跟踪候车室中的人数，遇到 ‘E’ 就递增，遇到 ‘L’ 就递减。
  • 答案是任何时刻候车室中的最大人数。

解题思路

这是一道模拟题，核心思想是跟踪候车室中人数的变化并记录峰值。

解题思路：

  1. 模拟过程：遍历字符串，维护当前候车室中的人数

    • 遇到 ‘E’：有人进入，人数 +1
    • 遇到 ‘L’：有人离开，人数 -1

  2. 记录最大值：在模拟过程中，实时更新并记录候车室中人数的最大值，这个最大值就是所需的最少椅子数

  3. 关键洞察：由于每个进入的人都需要一张椅子，所需椅子数等于同时在候车室中的最大人数。当人数达到峰值时，就是椅子需求最大的时刻。

算法步骤：

  • 初始化当前人数为 0，最大人数为 0
  • 遍历字符串的每个字符
  • 根据字符更新当前人数
  • 更新最大人数记录
  • 返回最大人数

时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int minimumChairs(string s) {
        int current = 0, maxChairs = 0;
        for (char c : s) {
            if (c == 'E') {
                current++;
                maxChairs = max(maxChairs, current);
            } else {
                current--;
            }
        }
        return maxChairs;
    }
};

class Solution:
    def minimumChairs(self, s: str) -> int:
        current = 0
        max_chairs = 0
        for c in s:
            if c == 'E':
                current += 1
                max_chairs = max(max_chairs, current)
            else:
                current -= 1
        return max_chairs

public class Solution {
    public int MinimumChairs(string s) {
        int current = 0, maxChairs = 0;
        foreach (char c in s) {
            if (c == 'E') {
                current++;
                maxChairs = Math.Max(maxChairs, current);
            } else {
                current--;
            }
        }
        return maxChairs;
    }
}

var minimumChairs = function(s) {
    let currentPeople = 0;
    let maxChairs = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'E') {
            currentPeople++;
            maxChairs = Math.max(maxChairs, currentPeople);
        } else {
            currentPeople--;
        }
    }
    
    return maxChairs;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，其中 n 是字符串长度
空间复杂度O(1)只使用常数个变量存储当前人数和最大人数

相关题目