思考量不小不大，这才叫中等 👍
题面
给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示：
- 如果第
i个字符是'Y'，它表示第i小时有顾客到达。 - 如果第
i个字符是'N'，它表示第i小时没有顾客到达。
如果商店在第 j 小时关门（0 <= j <= n），代价按如下方式计算：
- 在开门期间，如果某一个小时没有顾客到达，代价增加
1。 - 在关门期间，如果某一个小时有顾客到达，代价增加
1。
请你返回在确保代价 最小 的前提下，商店的 最早 关门时间。
注意，商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。
示例 1：
输入： customers = “YYNY”
输出： 2
解释：
第 0 小时关门，总共 1+1+0+1 = 3 代价。
第 1 小时关门，总共 0+1+0+1 = 2 代价。
第 2 小时关门，总共 0+0+0+1 = 1 代价。
第 3 小时关门，总共 0+0+1+1 = 2 代价。
第 4 小时关门，总共 0+0+1+0 = 1 代价。
在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早，所以最优关门时间是 2 。
示例 2：
输入： customers = “NNNNN”
输出： 0
解释： 最优关门时间是 0 ，因为自始至终没有顾客到达。
示例 3：
输入： customers = “YYYY”
输出： 4
解释： 最优关门时间是 4 ，因为每一小时均有顾客到达。
提示：
- 1 <=
customers.length<= $10^5$ customers只包含字符'Y'和'N'。
思路
使用前缀和思想，用两个变量分别统计 开门N 和 关门Y 的代价，并且进行前后各一次轮询，记录各时间节点关门时的代价数。
（其实应该还有优化空间）
代码
鉴于题里面第 30 几个测试用例的输入长的逆天，所以注释掉了调试的 printf 部分。
class Solution {
public:
int bestClosingTime(string customers) {
int minn = INT_MAX;
int minn_indicator = 0;
int counts[100005];
int open_n_count = 0;
int close_y_count = 0;
memset(counts, 0, sizeof(counts));
for(int i=1;i<customers.length();i++){
if(customers[i-1] == 'N'){
open_n_count++;
}
// printf("N before %d: %d\n", i, open_n_count);
counts[i] = open_n_count;
}
for(int i=customers.length()-1;i>=0;i--){
if(customers[i] == 'Y'){
close_y_count++;
}
// printf("Y in and after %d: %d\n", i, close_y_count);
counts[i] += close_y_count;
}
int ans = 0;
int ans_count = INT_MAX;
// printf("Time %lu: costs %d\n", customers.length(), open_n_count);
for(int i=customers.length()-1;i>=0;i--){
// printf("Time %d: costs %d\n",i,counts[i]);
if(counts[i]<=ans_count){
// printf("%d <= %d\n",counts[i], ans_count);
ans = i;
ans_count = counts[i];
}
}
if(open_n_count < ans_count){
ans = customers.length();
}
return ans;
}
};
最终结果 15ms 。
后记
放一段 0ms 的参考实现，叹为观止。
class Solution {
public:
int bestClosingTime(string customers) {
int penalty = 0, min_penalty = 0, ans = 0;
for (int i = 0; i < customers.size(); i++) {
penalty += customers[i] == 'N' ? 1 : -1;
if (penalty < min_penalty) {
min_penalty = penalty;
ans = i + 1;
}
}
return ans;
}
};