Problem#
給你一個由 Y 和 N 組成的字串 customers 其中第 $i$ 個字元 customers[i] 代表第 $i$ 個小時有沒有客人來
令 $j$ 等於關店的時間，有兩條規則：
- 如果店開著的時候沒有客人來的話，扣一點
- 如果有客人在店關了之後來的話，扣一點
問你能不能回傳最早的小時，其扣點最大？
測資限制#
- $1 \le n \le 10^5$: 字串長度，只包含
Y,N
想法#
-
暴力：枚舉 $j=[0, n-1]$ 關店的時間，跟著規則統計 $O(n^2)$ -> TLE
-
用前綴和可以在 $O(1)$ 查詢得知區間的
Y或N的數量，需花費 $O(n)$ 構建陣列 -
時間複雜度: $\mathcal{O}(n)$
-
空間複雜度: $\mathcal{O}(n)$