解題說明
Minimum Penalty for a Shop
題目描述：
給定一個由 'Y' 和 'N' 組成的字串 customers，customers[i] 表示第 i 小時是否有客戶到來。商店在某小時 j 關門（意味著第 0 到 j-1 小時營業）。罰款計算為：
- 營業時沒有客戶到來的小時數（
'N'的數量，0 到 j-1） - 關門後有客戶到來的小時數（
'Y'的數量，j 到 n-1）
求罰款最小的關門時間 j。若有多個，取最小的 j。
解題思路：
- 總罰款 =
j之前的'N'數量 +j之後的'Y'數量。 - 先計算在第 0 小時關門（j=0）的罰款：等於整個字串中
'Y'的總數。 - 從 j=0 到 j=n 逐步移動關門時間：
- 若
customers[j] == 'Y'：罰款 -1（少了一個關門後的 Y） - 若
customers[j] == 'N'：罰款 +1（多了一個營業時的 N）
- 若
- 記錄過程中的最小罰款及其位置。
C++ 解法
複雜度分析
時間複雜度：O(n) — 兩次遍歷字串（一次計算初始罰款，一次掃描最優關門時間）。
空間複雜度：O(1) — 只使用常數額外空間。
虛擬碼
1. Count total 'Y' in customers -> initial penalty (closing at hour 0)
2. Set minPenalty = penalty, bestTime = 0
3. For j from 0 to n-1:
a. If customers[j] == 'Y': penalty -= 1
b. Else: penalty += 1
c. If penalty < minPenalty:
- minPenalty = penalty, bestTime = j + 1
4. Return bestTime其他解法
前綴和法 O(n)：預計算 'N' 的前綴和與 'Y' 的後綴和，對每個 j 計算 prefixN[j] + suffixY[j]。需要 O(n) 額外空間。
暴力法 O(n^2)：對每個可能的關門時間 j，遍歷計算罰款。時間複雜度過高。
延伸思考
- 如果每個小時的罰款權重不同（例如有客戶但不營業的罰款更高），做法如何調整？
- 如果允許在一天中多次開關門（多個營業時段），問題如何建模？
- 此題的罰款增減規律與「最大子陣列和」（Kadane's Algorithm）有何相似性？