LeetCode 2483 店铺最小罚款（Minimum Penalty for a Shop）：前缀后缀统计与四类扫描解法精讲

LeetCode 2483 店铺最小罚款（Minimum Penalty for a Shop）：前缀后缀统计与四类扫描解法精讲

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本指南围绕 LeetCode 2483「店铺最小罚款」（Minimum Penalty for a Shop）展开，系统讲解如何根据店铺的顾客到访日志（'Y'/'N' 字符串）求出使罚款最小的打烊时刻。文章覆盖暴力枚举、前缀和与后缀和、两遍扫描、单遍扫描四类解法的完整推导、多语言实现与复杂度分析，并结合本仓库 cpp/2483-minimum-penalty-for-a-shop.cpp、java/2483-minimum-penalty-for-a-shop.java、kotlin/2483-minimum-penalty-for-a-shop.kt、python/2483-minimum-penalty-for-a-shop.py 的源码实现进行印证。读完本文，你将掌握将字符串计数问题转化为前缀/后缀累加问题、再进一步压缩为常数空间的完整套路。

问题定义与罚则语义

题目给出一条0索引字符串customers，只包含字符'Y'与'N'：

• 第i个字符为'Y'，表示第i小时有顾客到店；
• 第i个字符为'N'，表示第i小时没有顾客到店。

若店铺在第j小时（0 <= j <= n，n为字符串长度）打烊，罚款计算规则如下：

1. 营业但无人到店：店铺营业的每个小时里，若没有顾客来，罚款+1；
2. 打烊但顾客到店：店铺打烊的每个小时里，若有顾客来，罚款+1。

要求返回罚款最小时最早的打烊时刻。仓库 C++ 源码 cpp/2483-minimum-penalty-for-a-shop.cpp 的头部注释完整描述了上述规则，并给出了标准示例：

Input: customers = "YYNY" Output: 2

逐步核算（来自 cpp/2483-minimum-penalty-for-a-shop.cpp）：

• 第0小时打烊：1+1+0+1 = 3（全程打烊，错过 3 个 'Y'）；
• 第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小时均取得最小罚款1，按题意返回更早的时刻2。

关键语义：店铺在第j小时打烊，表示它在第j小时起关闭——即营业时段为0到j-1，关闭时段为j到n-1。这是所有解法构造罚则的基础，一旦混淆极易产生 off-by-one 错误（详见文末「常见陷阱」）。

在 README.md 的题解完成表中，该题已收录 Python、Java、Kotlin、C++ 等多语言实现，本文下述四种解法与其逐一对应。

前置知识

• 前缀和（Prefix Sum）：预先统计每个位置之前的字符计数，使任意前缀区间的计数查询降到 O(1)；
• 后缀和（Suffix Sum）：预先统计从每个位置起往后的字符计数，与前缀和对称；
• 字符串顺序迭代：单次从左到右扫描，同时维护运行中的累加值；
• 贪心式最优追踪：遍历所有候选打烊时刻时，只保留当前见过的最小罚款及其时刻。

1. 暴力枚举（Brute Force）

思路

店铺可以在0到n（含）之间的任意时刻打烊。若在第i小时打烊，则：

• 位置0到i-1中的每个'N'计1分（营业却无人）；
• 位置i到n-1中的每个'Y'计1分（打烊却有人）。

枚举全部n+1个候选打烊时刻，取罚款最小者即可。

算法步骤

1. 初始化res与minPenalty为n（最坏情况下罚款不会超过n）；
2. 对每个候选打烊时刻i（0到n）：
   • 统计位置0到i-1中'N'的个数；
   • 统计位置i到n-1中'Y'的个数；
   • 两者之和即为该时刻的罚款；若小于minPenalty，则更新minPenalty与res；
3. 返回res。

多语言实现

class Solution: def bestClosingTime(self, customers: str) -> int: n = len(customers) res = n minPenalty = n for i in range(n + 1): penalty = 0 for j in range(i): if customers[j] == 'N': penalty += 1 for j in range(i, n): if customers[j] == 'Y': penalty += 1 if penalty < minPenalty: minPenalty = penalty res = i return res

public class Solution { public int bestClosingTime(String customers) { int n = customers.length(); int res = n, minPenalty = n; for (int i = 0; i <= n; i++) { int penalty = 0; for (int j = 0; j < i; j++) { if (customers.charAt(j) == 'N') { penalty++; } } for (int j = i; j < n; j++) { if (customers.charAt(j) == 'Y') { penalty++; } } if (penalty < minPenalty) { minPenalty = penalty; res = i; } } return res; } }

class Solution { public: int bestClosingTime(string customers) { int n = customers.size(); int res = n, minPenalty = n; for (int i = 0; i <= n; i++) { int penalty = 0; for (int j = 0; j < i; j++) { if (customers[j] == 'N') { penalty++; } } for (int j = i; j < n; j++) { if (customers[j] == 'Y') { penalty++; } } if (penalty < minPenalty) { minPenalty = penalty; res = i; } } return res; } };

class Solution { /** * @param {string} customers * @return {number} */ bestClosingTime(customers) { const n = customers.length; let res = n, minPenalty = n; for (let i = 0; i <= n; i++) { let penalty = 0; for (let j = 0; j < i; j++) { if (customers[j] === 'N') { penalty++; } } for (let j = i; j < n; j++) { if (customers[j] === 'Y') { penalty++; } } if (penalty < minPenalty) { minPenalty = penalty; res = i; } } return res; } }

public class Solution { public int BestClosingTime(string customers) { int n = customers.Length; int res = n, minPenalty = n; for (int i = 0; i <= n; i++) { int penalty = 0; for (int j = 0; j < i; j++) { if (customers[j] == 'N') { penalty++; } } for (int j = i; j < n; j++) { if (customers[j] == 'Y') { penalty++; } } if (penalty < minPenalty) { minPenalty = penalty; res = i; } } return res; } }

func bestClosingTime(customers string) int { n := len(customers) res, minPenalty := n, n for i := 0; i <= n; i++ { penalty := 0 for j := 0; j < i; j++ { if customers[j] == 'N' { penalty++ } } for j := i; j < n; j++ { if customers[j] == 'Y' { penalty++ } } if penalty < minPenalty { minPenalty = penalty res = i } } return res }

class Solution { fun bestClosingTime(customers: String): Int { val n = customers.length var res = n var minPenalty = n for (i in 0..n) { var penalty = 0 for (j in 0 until i) { if (customers[j] == 'N') { penalty++ } } for (j in i until n) { if (customers[j] == 'Y') { penalty++ } } if (penalty < minPenalty) { minPenalty = penalty res = i } } return res } }

class Solution { func bestClosingTime(_ customers: String) -> Int { let n = customers.count let chars = Array(customers) var res = n var minPenalty = n for i in 0...n { var penalty = 0 for j in 0..<i { if chars[j] == "N" { penalty += 1 } } for j in i..<n { if chars[j] == "Y" { penalty += 1 } } if penalty < minPenalty { minPenalty = penalty res = i } } return res } }

impl Solution { pub fn best_closing_time(customers: String) -> i32 { let s = customers.as_bytes(); let n = s.len(); let mut res = n as i32; let mut min_penalty = n as i32; for i in 0..=n { let mut penalty = 0; for j in 0..i { if s[j] == b'N' { penalty += 1; } } for j in i..n { if s[j] == b'Y' { penalty += 1; } } if penalty < min_penalty { min_penalty = penalty; res = i as i32; } } res } }

复杂度

• 时间复杂度：$O(n^2)$——每个候选时刻i都要重新扫描两侧区间；
• 空间复杂度：$O(1)$——只使用常数个变量。

该解法思路直观、不易出错，适合作为正确性基准，但性能不足以应对大输入。

2. 前缀和与后缀和（Prefix & Suffix）

思路

暴力解在每个i处重复计数，造成平方复杂度。改进办法：预先算出每个位置之前的'N'个数（前缀），以及从每个位置往后的'Y'个数（后缀），则任意打烊时刻的罚款就是两个预计算值的和，查询降到 O(1)。

• prefixN[i]= 位置0到i-1中'N'的个数；
• suffixY[i]= 位置i到n-1中'Y'的个数。

算法步骤

1. 构建prefixN：从左到右扫描，先记录当前累计'N'数，遇到'N'再自增，最后补上末尾一项，数组长度为n+1；
2. 构建suffixY：从右到左扫描，先继承右侧累计值，遇到'Y'再自增；
3. 对每个打烊时刻i（0到n），罚款 =prefixN[i] + suffixY[i]，追踪最小罚款及其对应时刻；
4. 返回最小罚款对应的时刻。

仓库中的 Java 实现 java/2483-minimum-penalty-for-a-shop.java 正是这一思路：先构造pre_n（前缀'N'计数）与post_y（后缀'Y'计数），再以pre_n[i] + post_y[i]扫描取最小；Kotlin 实现 kotlin/2483-minimum-penalty-for-a-shop.kt 同样使用prefix与postfix两个数组完成。

多语言实现

class Solution: def bestClosingTime(self, customers: str) -> int: n = len(customers) cnt = 0 prefixN = [] for c in customers: prefixN.append(cnt) if c == 'N': cnt += 1 prefixN.append(cnt) suffixY = [0] * (n + 1) for i in range(n - 1, -1, -1): suffixY[i] = suffixY[i + 1] if customers[i] == 'Y': suffixY[i] += 1 res = n minPenalty = n for i in range(n + 1): penalty = prefixN[i] + suffixY[i] if penalty < minPenalty: minPenalty = penalty res = i return res

public class Solution { public int bestClosingTime(String customers) { int n = customers.length(); int cnt = 0; int[] prefixN = new int[n + 1]; for (int i = 0; i < n; i++) { prefixN[i] = cnt; if (customers.charAt(i) == 'N') { cnt++; } } prefixN[n] = cnt; int[] suffixY = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { suffixY[i] = suffixY[i + 1]; if (customers.charAt(i) == 'Y') { suffixY[i]++; } } int res = n, minPenalty = n; for (int i = 0; i <= n; i++) { int penalty = prefixN[i] + suffixY[i]; if (penalty < minPenalty) { minPenalty = penalty; res = i; } } return res; } }

class Solution { public: int bestClosingTime(string customers) { int n = customers.size(), cnt = 0; vector<int> prefixN(n + 1); for (int i = 0; i < n; i++) { prefixN[i] = cnt; if (customers[i] == 'N') { cnt++; } } prefixN[n] = cnt; vector<int> suffixY(n + 1, 0); for (int i = n - 1; i >= 0; i--) { suffixY[i] = suffixY[i + 1]; if (customers[i] == 'Y') { suffixY[i]++; } } int res = n, minPenalty = n; for (int i = 0; i <= n; i++) { int penalty = prefixN[i] + suffixY[i]; if (penalty < minPenalty) { minPenalty = penalty; res = i; } } return res; } };

class Solution { /** * @param {string} customers * @return {number} */ bestClosingTime(customers) { const n = customers.length; let cnt = 0; const prefixN = []; for (const c of customers) { prefixN.push(cnt); if (c === 'N') { cnt++; } } prefixN.push(cnt); const suffixY = new Array(n + 1).fill(0); for (let i = n - 1; i >= 0; i--) { suffixY[i] = suffixY[i + 1]; if (customers[i] === 'Y') { suffixY[i]++; } } let res = n, minPenalty = n; for (let i = 0; i <= n; i++) { const penalty = prefixN[i] + suffixY[i]; if (penalty < minPenalty) { minPenalty = penalty; res = i; } } return res; } }

public class Solution { public int BestClosingTime(string customers) { int n = customers.Length; int cnt = 0; int[] prefixN = new int[n + 1]; for (int i = 0; i < n; i++) { prefixN[i] = cnt; if (customers[i] == 'N') { cnt++; } } prefixN[n] = cnt; int[] suffixY = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { suffixY[i] = suffixY[i + 1]; if (customers[i] == 'Y') { suffixY[i]++; } } int res = n, minPenalty = n; for (int i = 0; i <= n; i++) { int penalty = prefixN[i] + suffixY[i]; if (penalty < minPenalty) { minPenalty = penalty; res = i; } } return res; } }

func bestClosingTime(customers string) int { n := len(customers) cnt := 0 prefixN := make([]int, n+1) for i := 0; i < n; i++ { prefixN[i] = cnt if customers[i] == 'N' { cnt++ } } prefixN[n] = cnt suffixY := make([]int, n+1) for i := n - 1; i >= 0; i-- { suffixY[i] = suffixY[i+1] if customers[i] == 'Y' { suffixY[i]++ } } res, minPenalty := n, n for i := 0; i <= n; i++ { penalty := prefixN[i] + suffixY[i] if penalty < minPenalty { minPenalty = penalty res = i } } return res }

class Solution { fun bestClosingTime(customers: String): Int { val n = customers.length var cnt = 0 val prefixN = IntArray(n + 1) for (i in 0 until n) { prefixN[i] = cnt if (customers[i] == 'N') { cnt++ } } prefixN[n] = cnt val suffixY = IntArray(n + 1) for (i in n - 1 downTo 0) { suffixY[i] = suffixY[i + 1] if (customers[i] == 'Y') { suffixY[i]++ } } var res = n var minPenalty = n for (i in 0..n) { val penalty = prefixN[i] + suffixY[i] if (penalty < minPenalty) { minPenalty = penalty res = i } } return res } }

class Solution { func bestClosingTime(_ customers: String) -> Int { let n = customers.count let chars = Array(customers) var cnt = 0 var prefixN = Int for i in 0..<n { prefixN[i] = cnt if chars[i] == "N" { cnt += 1 } } prefixN[n] = cnt var suffixY = Int for i in stride(from: n - 1, through: 0, by: -1) { suffixY[i] = suffixY[i + 1] if chars[i] == "Y" { suffixY[i] += 1 } } var res = n var minPenalty = n for i in 0...n { let penalty = prefixN[i] + suffixY[i] if penalty < minPenalty { minPenalty = penalty res = i } } return res } }

impl Solution { pub fn best_closing_time(customers: String) -> i32 { let s = customers.as_bytes(); let n = s.len(); let mut cnt = 0i32; let mut prefix_n = vec![0i32; n + 1]; for i in 0..n { prefix_n[i] = cnt; if s[i] == b'N' { cnt += 1; } } prefix_n[n] = cnt; let mut suffix_y = vec![0i32; n + 1]; for i in (0..n).rev() { suffix_y[i] = suffix_y[i + 1]; if s[i] == b'Y' { suffix_y[i] += 1; } } let mut res = n as i32; let mut min_penalty = n as i32; for i in 0..=n { let penalty = prefix_n[i] + suffix_y[i]; if penalty < min_penalty { min_penalty = penalty; res = i as i32; } } res } }

复杂度

• 时间复杂度：$O(n)$——两轮预计算各 O(n)，一轮扫描 O(n)；
• 空间复杂度：$O(n)$——两个长度为n+1的辅助数组。

这是「以空间换时间」的典型模式，也是许多区间查询问题的通用前置步骤。

3. 两遍扫描（Iteration, Two Pass）

思路

前缀/后缀解法的两个辅助数组本质上是冗余的：我们完全可以在一遍计数 + 一遍扫描中动态维护左右两侧的罚款贡献，从而把空间压到 O(1)。

先统计全部'Y'的个数cntY。若第0小时就打烊，店铺全程关闭，会错过所有顾客，此时罚款恰为cntY。随后从左到右推进打烊时刻：

• 每越过一个'Y'，说明这个顾客在打烊前被服务到，罚项减少1（cntY--）；
• 每越过一个'N'，说明这段时间营业却无人，罚项增加1（cntN++）。

扫描过程中，任意时刻的罚款恒等于cntN + cntY，只需记录其最小值。

算法步骤

1. 统计cntY为'Y'总数；初始化minPenalty = cntY、res = 0、cntN = 0；
2. 遍历下标i处的字符：
   • 若是'Y'，cntY--（少一个被错过的顾客）；
   • 若是'N'，cntN++（多一个白营业的小时）；
   • 计算当前罚款cntN + cntY；
   • 若小于minPenalty，更新minPenalty并把res置为i + 1；
3. 返回res。

多语言实现

class Solution: def bestClosingTime(self, customers: str) -> int: cntY = sum(c == "Y" for c in customers) minPenalty = cntY res = cntN = 0 for i, c in enumerate(customers): if c == "Y": cntY -= 1 else: cntN += 1 penalty = cntN + cntY if penalty < minPenalty: res = i + 1 minPenalty = penalty return res

public class Solution { public int bestClosingTime(String customers) { int cntY = 0; for (char c : customers.toCharArray()) { if (c == 'Y') cntY++; } int minPenalty = cntY, res = 0, cntN = 0; for (int i = 0; i < customers.length(); i++) { if (customers.charAt(i) == 'Y') { cntY--; } else { cntN++; } int penalty = cntN + cntY; if (penalty < minPenalty) { res = i + 1; minPenalty = penalty; } } return res; } }

class Solution { public: int bestClosingTime(string customers) { int cntY = count(customers.begin(), customers.end(), 'Y'); int minPenalty = cntY, res = 0, cntN = 0; for (int i = 0; i < customers.size(); i++) { if (customers[i] == 'Y') { cntY--; } else { cntN++; } int penalty = cntN + cntY; if (penalty < minPenalty) { res = i + 1; minPenalty = penalty; } } return res; } };

class Solution { /** * @param {string} customers * @return {number} */ bestClosingTime(customers) { let cntY = 0; for (let c of customers) { if (c === 'Y') cntY++; } let minPenalty = cntY, res = 0, cntN = 0; for (let i = 0; i < customers.length; i++) { if (customers[i] === 'Y') { cntY--; } else { cntN++; } const penalty = cntN + cntY; if (penalty < minPenalty) { res = i + 1; minPenalty = penalty; } } return res; } }

public class Solution { public int BestClosingTime(string customers) { int cntY = 0; foreach (char c in customers) { if (c == 'Y') cntY++; } int minPenalty = cntY, res = 0, cntN = 0; for (int i = 0; i < customers.Length; i++) { if (customers[i] == 'Y') { cntY--; } else { cntN++; } int penalty = cntN + cntY; if (penalty < minPenalty) { res = i + 1; minPenalty = penalty; } } return res; } }

func bestClosingTime(customers string) int { cntY := 0 for _, c := range customers { if c == 'Y' { cntY++ } } minPenalty, res, cntN := cntY, 0, 0 for i := 0; i < len(customers); i++ { if customers[i] == 'Y' { cntY-- } else { cntN++ } penalty := cntN + cntY if penalty < minPenalty { res = i + 1 minPenalty = penalty } } return res }

class Solution { fun bestClosingTime(customers: String): Int { var cntY = customers.count { it == 'Y' } var minPenalty = cntY var res = 0 var cntN = 0 for (i in customers.indices) { if (customers[i] == 'Y') { cntY-- } else { cntN++ } val penalty = cntN + cntY if (penalty < minPenalty) { res = i + 1 minPenalty = penalty } } return res } }

class Solution { func bestClosingTime(_ customers: String) -> Int { let chars = Array(customers) var cntY = chars.filter { $0 == "Y" }.count var minPenalty = cntY var res = 0 var cntN = 0 for i in 0..<chars.count { if chars[i] == "Y" { cntY -= 1 } else { cntN += 1 } let penalty = cntN + cntY if penalty < minPenalty { res = i + 1 minPenalty = penalty } } return res } }

impl Solution { pub fn best_closing_time(customers: String) -> i32 { let s = customers.as_bytes(); let mut cnt_y = s.iter().filter(|&&c| c == b'Y').count() as i32; let mut min_penalty = cnt_y; let mut res = 0i32; let mut cnt_n = 0i32; for i in 0..s.len() { if s[i] == b'Y' { cnt_y -= 1; } else { cnt_n += 1; } let penalty = cnt_n + cnt_y; if penalty < min_penalty { res = i as i32 + 1; min_penalty = penalty; } } res } }

复杂度

• 时间复杂度：$O(n)$——统计一遍、扫描一遍，各 O(n)；
• 空间复杂度：$O(1)$——仅使用三个计数器。

仓库中的 Python 实现 python/2483-minimum-penalty-for-a-shop.py 采用了与之同构但符号方向相反的变体：以'Y'减分、'N'加分维护curPenalty，并在curPenalty创新低时记录i+1，同样只需 O(1) 空间。

4. 单遍扫描（Iteration, One Pass）

思路

两遍扫描还能再进一步：不直接维护绝对罚款，而是维护一个相对分值。把'Y'视为+1（营业带来的收益），'N'视为-1（营业付出的成本），从左到右累加。直觉上，累计分值最高的点意味着「营业带来的净收益最大」，因此最优打烊时刻就是该最高点之后的那个小时。

数学上等价于：若在时刻i打烊，罚款 =（i之前'N'数）+（i之后'Y'数）。令T为总'Y'数，则罚款 =i前'N'数 +T - i前'Y'数 =T + (i 前 N 数 - i 前 Y 数)。括号内正是以'N'=-1, 'Y'=+1计分时的前缀和取负。因此最小化罚款等价于最大化该前缀和，最优时刻落在前缀和首次达到最大值的边界处。

仓库中 C++ 实现 cpp/2483-minimum-penalty-for-a-shop.cpp 正是这种写法：'Y'使pen自增、'N'使pen自减，当pen刷新最大值时记录i，最终返回++res（即最高点后的小时）。Kotlin 文件 kotlin/2483-minimum-penalty-for-a-shop.kt 也给出了同样的「Kadane 风格」单遍版本。

算法步骤

1. 初始化res = 0、minPenalty = 0、penalty = 0；
2. 遍历下标i处的字符：
   • 若是'Y'，penalty += 1；否则penalty -= 1；
   • 若penalty > minPenalty，更新minPenalty = penalty，并令res = i + 1；
3. 返回res。

注意更新条件是严格大于（>），且res记录的是累计分值创新高之后的位置，即i+1；初始时刻0（penalty = 0）天然是候选，无需特判。

多语言实现

class Solution: def bestClosingTime(self, customers: str) -> int: res = minPenalty = 0 penalty = 0 for i, c in enumerate(customers): penalty += 1 if c == 'Y' else -1 if penalty > minPenalty: minPenalty = penalty res = i + 1 return res

public class Solution { public int bestClosingTime(String customers) { int res = 0, minPenalty = 0, penalty = 0; for (int i = 0; i < customers.length(); i++) { penalty += customers.charAt(i) == 'Y' ? 1 : -1; if (penalty > minPenalty) { minPenalty = penalty; res = i + 1; } } return res; } }

class Solution { public: int bestClosingTime(string customers) { int res = 0, minPenalty = 0, penalty = 0; for (int i = 0; i < customers.size(); i++) { penalty += customers[i] == 'Y' ? 1 : -1; if (penalty > minPenalty) { minPenalty = penalty; res = i + 1; } } return res; } };

class Solution { /** * @param {string} customers * @return {number} */ bestClosingTime(customers) { let res = 0, minPenalty = 0, penalty = 0; for (let i = 0; i < customers.length; i++) { penalty += customers[i] === 'Y' ? 1 : -1; if (penalty > minPenalty) { minPenalty = penalty; res = i + 1; } } return res; } }

public class Solution { public int BestClosingTime(string customers) { int res = 0, minPenalty = 0, penalty = 0; for (int i = 0; i < customers.Length; i++) { penalty += customers[i] == 'Y' ? 1 : -1; if (penalty > minPenalty) { minPenalty = penalty; res = i + 1; } } return res; } }

func bestClosingTime(customers string) int { res, minPenalty, penalty := 0, 0, 0 for i := 0; i < len(customers); i++ { if customers[i] == 'Y' { penalty++ } else { penalty-- } if penalty > minPenalty { minPenalty = penalty res = i + 1 } } return res }

class Solution { fun bestClosingTime(customers: String): Int { var res = 0 var minPenalty = 0 var penalty = 0 for (i in customers.indices) { penalty += if (customers[i] == 'Y') 1 else -1 if (penalty > minPenalty) { minPenalty = penalty res = i + 1 } } return res } }

class Solution { func bestClosingTime(_ customers: String) -> Int { let chars = Array(customers) var res = 0 var minPenalty = 0 var penalty = 0 for i in 0..<chars.count { penalty += chars[i] == "Y" ? 1 : -1 if penalty > minPenalty { minPenalty = penalty res = i + 1 } } return res } }

impl Solution { pub fn best_closing_time(customers: String) -> i32 { let s = customers.as_bytes(); let mut res = 0i32; let mut min_penalty = 0i32; let mut penalty = 0i32; for i in 0..s.len() { penalty += if s[i] == b'Y' { 1 } else { -1 }; if penalty > min_penalty { min_penalty = penalty; res = i as i32 + 1; } } res } }

复杂度

• 时间复杂度：$O(n)$——仅一轮扫描；
• 空间复杂度：$O(1)$——只使用三个变量。

这是本题的最优解：一次遍历、常数空间、代码最短，适合作为面试中的最终答案。

四解法复杂度对比

四种解法最终都返回罚款最小时最早的打烊时刻，输出一致；区别只在于计算罚款的方式与时空开销。

常见陷阱

1. 混淆打烊时刻的语义

店铺在第i小时打烊，表示营业时段为0到i-1、关闭时段为i到n-1。很多实现错误地把它理解成「第i小时仍在营业」，导致罚则计算整体错位，产生 off-by-one 错误。建议先在纸上用"YYNY"逐步核算（见文首示例）再编码。

2. 漏掉第0小时或第n小时

合法打烊时刻覆盖0（全天不营业）到n（全天营业）。若循环范围写成1..n-1之类的区间，就会漏掉「最优策略是干脆不开门」或「干脆开满全天」这两种情况，得到错误答案。三种线性解法均通过循环i从0到n（含）规避此问题。

3. 平局时返回了错误的索引

当多个打烊时刻罚款相同且都是最小时，题目要求返回最早的一个。实现上若用<=而非<更新结果，或扫描顺序不正确，就会把答案覆盖成更晚的时刻。因此务必使用严格小于（<）才更新res，保证只保留首次遇到的最优解。

仓库源码印证

本仓库为本题提供了多语言、多思路的实现，可在 README.md 的完成状态表中确认收录情况，具体包括：

• cpp/2483-minimum-penalty-for-a-shop.cpp：头部注释完整给出题目罚则与"YYNY"手算示例，正文采用解法 4（单遍扫描，O(N)时间、O(1)空间）；
• java/2483-minimum-penalty-for-a-shop.java：采用解法 2（前缀pre_n+ 后缀post_y）；
• kotlin/2483-minimum-penalty-for-a-shop.kt：同时给出解法 2（前缀/后缀数组）与解法 4（Kadane 风格单遍扫描）两版实现；
• python/2483-minimum-penalty-for-a-shop.py：单遍扫描的符号反转变体，以curPenalty创新低处记录i+1。

对照阅读可以发现，四种解法的核心差异仅在于「如何得到某个时刻的罚款」：暴力重扫、前缀后缀查表、两计数器动态维护、单变量相对分值。掌握这条从 O(n²) 到 O(n) 再到 O(1) 空间的优化主线，就理解了本题的全部考查点，也能将其迁移到其他「前缀/后缀统计 + 最优分割点」类问题（如分割数组、平衡括号区间等）中。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode