1052. 愛生氣的書店老板
今天捺癞，書店老板有一家店打算試營(yíng)業(yè) customers.length 分鐘。每分鐘都有一些顧客（customers[i]）會(huì)進(jìn)入書店拦耐，所有這些顧客都會(huì)在那一分鐘結(jié)束后離開婶希。
在某些時(shí)候溉愁，書店老板會(huì)生氣。 如果書店老板在第 i 分鐘生氣饲趋，那么 grumpy[i] = 1拐揭，否則 grumpy[i] = 0。 當(dāng)書店老板生氣時(shí)奕塑，那一分鐘的顧客就會(huì)不滿意堂污，不生氣則他們是滿意的。
書店老板知道一個(gè)秘密技巧龄砰，能抑制自己的情緒盟猖，可以讓自己連續(xù) X 分鐘不生氣，但卻只能使用一次换棚。
請(qǐng)你返回這一天營(yíng)業(yè)下來式镐，最多有多少客戶能夠感到滿意的數(shù)量。
示例：
輸入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
輸出：16
解釋：
書店老板在最后 3 分鐘保持冷靜固蚤。
感到滿意的最大客戶數(shù)量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
題解：
本題考查的是滑動(dòng)窗口娘汞，其長(zhǎng)度固定為X。
首先這種思想?yún)⒖嫉氖牵?a target="_blank">這位大佬
我們需要查找這么一個(gè)長(zhǎng)度為X的窗口：窗口內(nèi)能留住更多的原本因?yàn)槔习迳鷼舛悔s走的顧客夕玩。最終最多能滿意的顧客數(shù)量=窗口內(nèi)留住的顧客最大值+所有不生氣時(shí)間的顧客你弦。
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int n = customers.length;
int sum = 0; //不生氣時(shí)間的顧客總數(shù)
for (int i = 0; i < n; i++) {
if (grumpy[i] == 0) {
sum += customers[i];
}
}
int curValue = 0; //當(dāng)前窗口內(nèi)不滿意顧客的數(shù)量
for (int i = 0; i < X; i++) { //前K分鐘不滿意顧客數(shù)量
if (grumpy[i] == 1) {
curValue += customers[i];
}
}
int resValue = curValue;
for (int i = X; i < n; i++) { //開始滑動(dòng)窗口
if (grumpy[i] == 1) { //新進(jìn)入窗口的元素
curValue += customers[i];
}
if (grumpy[i - X] == 1) { //離開窗口的元素
curValue -= customers[i - X];
}
resValue = Math.max(resValue, curValue);
}
return sum + resValue;
}
還有另外一種思想：
首先求出[0,X-1]窗口內(nèi)滿意顧客的人數(shù)，開始向右滑動(dòng)燎孟，進(jìn)來一個(gè)新的禽作，出去一個(gè)，求出滿意顧客的數(shù)量揩页，更新最大值旷偿。
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int ans = 0;
int sum = 0;
for (int i = 0; i < X; i++) { //開始窗口內(nèi)顧客滿意數(shù)量
sum += customers[i];
}
for (int i = X; i < customers.length; i++) { //開始窗口外顧客滿意數(shù)量
sum += (grumpy[i] == 0) ? customers[i] : 0;
}
ans = sum;
for (int i = 1; i <= customers.length - X; i++) {
sum -= customers[i - 1] * grumpy[i - 1];
sum += customers[i - 1 + X] * grumpy[i - 1 + X];
ans = Math.max(ans, sum);
}
return ans;
}
