Skip to content

Latest commit

 

History

History
323 lines (275 loc) · 6.21 KB

README.md

File metadata and controls

323 lines (275 loc) · 6.21 KB
comments difficulty edit_url rating source tags
true
简单
1211
第 400 场周赛 Q1
字符串
模拟

3168. 候诊室中的最少椅子数

English Version

题目描述

给你一个字符串 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 表示一个有效的进出序列。

解法

方法一：模拟

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

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

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

Python3

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

Java

class Solution {
    public int minimumChairs(String s) {
        int cnt = 0, left = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == 'E') {
                if (left > 0) {
                    --left;
                } else {
                    ++cnt;
                }
            } else {
                ++left;
            }
        }
        return cnt;
    }
}

C++

class Solution {
public:
    int minimumChairs(string s) {
        int cnt = 0, left = 0;
        for (char& c : s) {
            if (c == 'E') {
                if (left > 0) {
                    --left;
                } else {
                    ++cnt;
                }
            } else {
                ++left;
            }
        }
        return cnt;
    }
};

Go

func minimumChairs(s string) int {
	cnt, left := 0, 0
	for _, c := range s {
		if c == 'E' {
			if left > 0 {
				left--
			} else {
				cnt++
			}
		} else {
			left++
		}
	}
	return cnt
}

TypeScript

function minimumChairs(s: string): number {
    let [cnt, left] = [0, 0];
    for (const c of s) {
        if (c === 'E') {
            if (left > 0) {
                --left;
            } else {
                ++cnt;
            }
        } else {
            ++left;
        }
    }
    return cnt;
}