字符串customers只包含’Y’和’N’两种字母, 表示 i 时刻商店是否有客人来。
如果商店在 i 时刻处于开门状态，'Y’的代价是0，'N’的代价是1.（开门了却没有客人就算损失）。
反之，在 i 时刻处于关门状态，'N’的代价是0，'Y’的代价是1.（关门却有客人来也是损失）。
如果商店在 j 时刻关门，那么从 j 时刻到最后都是关门状态。
问在哪个时刻关门代价最小。
思路：
方法一：
先计算一直在关门状态（0时刻关门）的代价。
然后把关门的时间右移，这时候只需要在上一步代价的基础上改变前一时刻的代价值。
举个例子，看Example1.
先计算0时刻关门的代价为3.
然后关门时刻移动到时刻1，这时时刻1后面还是关门状态，代价上没有变化，有变化的是0时刻的关门状态变成了开门状态。
这时候需要修改0时刻的代价，0时刻是’Y’, 关门时代价是1，开门代价是0，关门到开门状态需要减去代价1.
这时在上一步代价3的基础上减去多出来的代价1. 所以时刻1的代价为3-1=2.
后面依次类推。
直到移动到字符串最右边（边界外，表示一直开门）。
这个过程中记下最小代价和对应的时刻。
public int bestClosingTime(String customers) {
char[] chs = customers.toCharArray();
int cntY = 0;
int cntN = 0;
int n = chs.length;
int[] penalty = new int[n+1];
int minP = 0;
int minIdx = 0;
//从0时刻起不开门的代价
for(int i = n-1; i >= 0; i--) {
if(chs[i] == 'Y'){
cntY ++;
penalty[i] = penalty[i+1] + 1;
} else {
cntN ++;
penalty[i] = penalty[i+1];
}
}
if(cntY == n) return n;
if(cntN == n) return 0;
//i时刻关门
minP = penalty[0];
for(int i = 1; i <= n; i++) {
if(chs[i-1] == 'Y') penalty[i] = penalty[i-1]-1;
else penalty[i] = penalty[i-1]+1;
if(penalty[i] < minP) {
minP = penalty[i];
minIdx = i;
}
}
return minIdx;
}
方法二：
其实不需要计算初始0时刻关门的代价。
因为它是多少并不影响结果。
还是Example1。我们把0～最后时刻关门的代价排列一下：
3, 2, 1, 2, 1
第2时刻代价最小，选在第2时刻关门。
这时，把初始时刻关门的代价由3改到0，后面还是和方法1一样，改变前一时刻的代价，于是得到
0, -1, -2, -1, -2
结果还是第2时刻代价最小。所以初始0时刻关门代价是多少都无所谓，只要后面能得到代价最小的时刻即可。
省去方法一中计算0时刻关门的代价，默认0时刻关门代价是0.
然后右移关门时刻 i , 每移一步，改变前一时刻的代价。比如移到1时，改变0时刻的代价。
0时刻是’Y’, 关门代价是1，开门代价是0，现在开门了需要把代价-1，反之如果是’N’就+1.
右移的过程中记录下最小代价和对应的时刻。
public int bestClosingTime(String customers) {
char[] a = customers.toCharArray();
int n = a.length;
int j = -1, penalty = 0, minP = 0;
for (int i = 0; i < a.length; i++) {
penalty += a[i] == 'Y'? -1 : 1;
if (penalty < minP) {
j = i;
minP = penalty;
}
}
return j + 1;
}
