題目描述:
給定一個由 'Y' 和 'N' 組成的字串 customers,customers[i] 表示第 i 小時是否有客戶到來。商店在某小時 j 關門(意味著第 0 到 j-1 小時營業)。罰款計算為:
'N' 的數量,0 到 j-1)'Y' 的數量,j 到 n-1)求罰款最小的關門時間 j。若有多個,取最小的 j。
解題思路:
j 之前的 'N' 數量 + j 之後的 'Y' 數量。'Y' 的總數。customers[j] == 'Y':罰款 -1(少了一個關門後的 Y)customers[j] == 'N':罰款 +1(多了一個營業時的 N)時間複雜度: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,遍歷計算罰款。時間複雜度過高。