LeetCode 题解工作台
商店的最少代价
给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示： 如果第 i 个字符是 'Y' ，它表示第 i 小时有顾客到达。 如果第 i 个字符是 'N' ，它表示第 i 小时没有顾客到达。 如果商店在第 j 小时关门（ 0 ），代价按如下…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
如果商店在第 小时关门，那么代价为 中字符 `'Y'` 的数量，我们初始化答案变量 为 ，代价变量 为 中字符 `'Y'` 的数量。 接下来，我们枚举商店在第 小时关门（$1 \leq j \leq n$）。如果 $\textit{customers}[j - 1]$ 为 `'N'`，说明在开门期间没有顾客到达，代价增加 ；否则说明在关门期间有顾客到达，代价减少 。如果当前代价 小于…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示：
- 如果第
i个字符是'Y'，它表示第i小时有顾客到达。 - 如果第
i个字符是'N'，它表示第i小时没有顾客到达。
如果商店在第 j 小时关门（0 <= j <= n），代价按如下方式计算：
- 在开门期间，如果某一个小时没有顾客到达，代价增加
1。 - 在关门期间，如果某一个小时有顾客到达，代价增加
1。
请你返回在确保代价 最小 的前提下，商店的 最早 关门时间。
注意，商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。
示例 1：
输入：customers = "YYNY" 输出：2 解释： - 第 0 小时关门，总共 1+1+0+1 = 3 代价。 - 第 1 小时关门，总共 0+1+0+1 = 2 代价。 - 第 2 小时关门，总共 0+0+0+1 = 1 代价。 - 第 3 小时关门，总共 0+0+1+1 = 2 代价。 - 第 4 小时关门，总共 0+0+1+0 = 1 代价。 在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早，所以最优关门时间是 2 。
示例 2：
输入：customers = "NNNNN" 输出：0 解释：最优关门时间是 0 ，因为自始至终没有顾客到达。
示例 3：
输入：customers = "YYYY" 输出：4 解释：最优关门时间是 4 ，因为每一小时均有顾客到达。
提示：
1 <= customers.length <= 105customers只包含字符'Y'和'N'。
解题思路
方法一：枚举
如果商店在第 小时关门，那么代价为 中字符 'Y' 的数量，我们初始化答案变量 为 ，代价变量 为 中字符 'Y' 的数量。
接下来，我们枚举商店在第 小时关门（）。如果 为 'N'，说明在开门期间没有顾客到达，代价增加 ；否则说明在关门期间有顾客到达，代价减少 。如果当前代价 小于最小代价 ，我们将答案变量 更新为 ，并将最小代价 更新为当前代价 。
遍历结束后，返回答案变量 即可。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
class Solution:
def bestClosingTime(self, customers: str) -> int:
ans = 0
mn = cost = customers.count("Y")
for j, c in enumerate(customers, 1):
cost += 1 if c == "N" else -1
if cost < mn:
ans, mn = j, cost
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each character is processed once for prefix and suffix counts. Space complexity is O(1) if using running counts instead of full prefix arrays. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Expect O(n) solution using prefix sums rather than nested loops.
- question_mark
Watch for off-by-one errors in computing suffix counts of 'Y'.
- question_mark
Early return for cases where all customers are 'N' or 'Y' may be discussed.
常见陷阱
外企场景- error
Confusing prefix sum of 'N' with suffix sum of 'Y', leading to incorrect penalties.
- error
Forgetting to include the case when the shop closes at the last hour.
- error
Incorrectly returning the last minimum instead of the earliest minimum hour.
进阶变体
外企场景- arrow_right_alt
Calculate maximum penalty hour instead of minimum for analytical contrast.
- arrow_right_alt
Handle multiple shops' customer strings simultaneously with the same approach.
- arrow_right_alt
Allow dynamic updates to customer string and recalculate optimal closing hour efficiently.