https://leetcode.com/problems/minimum-penalty-for-a-shop/description/
2483. Minimum Penalty for a Shop
給你一個陣列 customers，customers[i] 表示第 i 個小時的時候是否有顧客來消費
，開店的時候如果沒客人會虧損，關店的時候有客人來也會虧，我們要挑選一個時間
打烊可以讓店裡的虧損最低，並且這個時間要盡可能的早。
Example 1:
Input: customers = "YYNY"
Output: 2
Explanation:
- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is
earlier, the optimal closing time is 2.
Example 2:
Input: customers = "NNNNN"
Output: 0
Explanation: It is best to close the shop at the 0th hour as no customers
arrive.
思路：
1.先統計出所有小時關店時，會錯過或沒客人的數量，關店的時間點之前的
虧損會是該個時間點之前N的數量，而關店的時間點之後的虧損會是來客數量Y。
2.統計完之後從 "開到最後一刻才打烊" 遍歷到 "一開始就不開店" 的所有結果中
，取出最小的虧損額，因為我們是從比較晚的時間開始往前算所以遇到一樣虧損的
打烊時間就取新的就一定是時間最早的。
Java Code：
----------------------------------------
class Solution {
public int bestClosingTime(String customers) {
int n = customers.length();
int[] no = new int[n];
int[] yes = new int[n];
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += customers.charAt(i) == 'N' ? 1 : 0;
no[i] = cnt;
}
cnt = 0;
for (int i = n - 1; i >= 0; i--) {
cnt += customers.charAt(i) == 'Y' ? 1 : 0;
yes[i] = cnt;
}
int minPenalty = no[n - 1];
int hour = n;
for (int i = n - 1; i > 0; i--) {
int currPenalty = no[i - 1] + yes[i];
if (minPenalty >= currPenalty) {
minPenalty = currPenalty;
hour = i;
}
}
if (minPenalty >= yes[0]) {
return 0;
}
return hour;
}
}
----------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1693321095.A.5B8.html