Description
給定字串
customers，其中customers[i]為'Y'（有客人）或'N'（沒客人）。選擇一個關店時間j（0 到 n），penalty 等於：關門前沒客人的小時數 + 關門後有客人的小時數。回傳使 penalty 最小的最早關店時間。
Example:
Input: customers = “YYNY” Output: 2 （在 hour 2 關店，penalty = 0 (關門前無 N) + 1 (關門後有 Y) = 1，最小）
Intuition#
核心思路：在時間
j關店的 penalty = 前 j 小時中'N'的數量 + 後 n-j 小時中'Y'的數量。用 Prefix Sum 或 Running Count 找最小值。
- penalty(j) = prefix_N(j) + suffix_Y(j)
- suffix_Y(j) = total_Y - prefix_Y(j)
- 所以 penalty(j) = prefix_N(j) + total_Y - prefix_Y(j)
- 可以用一個變量追蹤 penalty 的變化
Approaches#
1: Prefix Sum#
- 概念: 預計算
'Y'的總數，遍歷每個關店時間計算 penalty - 時間複雜度:
O(n)- 兩次遍歷 - 空間複雜度:
O(1)- 常數空間
class Solution {
fun bestClosingTime(customers: String): Int {
val totalY = customers.count { it == 'Y' }
var prefixN = 0
var prefixY = 0
var minPenalty = totalY // j = 0 時的 penalty
var bestTime = 0
for (j in 1..customers.length) {
if (customers[j - 1] == 'N') prefixN++
else prefixY++
val penalty = prefixN + totalY - prefixY
if (penalty < minPenalty) {
minPenalty = penalty
bestTime = j
}
}
return bestTime
}
}⭐2: Running Score (One-Pass)#
- 概念: 觀察 penalty 的變化：從 j 到 j+1，若
customers[j] == 'Y'則 penalty 減 1（少一個關門後的 Y），若'N'則 penalty 加 1（多一個關門前的 N）。追蹤 running score 找最小值 - 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
O(1)- 常數空間
class Solution {
fun bestClosingTime(customers: String): Int {
var score = 0 // penalty 相對於初始值的變化量
var minScore = 0
var bestTime = 0
for (j in customers.indices) {
// 從 j 移到 j+1 的 penalty 變化
score += if (customers[j] == 'Y') -1 else 1
if (score < minScore) {
minScore = score
bestTime = j + 1
}
}
return bestTime
}
}Running Score 的巧妙之處：不需要計算絕對 penalty，只追蹤相對變化量。遇到
'Y'代表「關門後少一個客人的懲罰」所以 -1，遇到'N'代表「關門前多一個空閒的懲罰」所以 +1。找累計最小值的位置就是答案。
🔑 Takeaways#
- Pattern: 最佳分割點問題 -> Prefix Sum 或 Running Score 找最小值位置
- 關鍵技巧: 將問題轉化為「差值累計的最小值」避免計算絕對值，類似於 Maximum Subarray 的 Kadane 思維