題目描述
leetcode 第1052題：愛生氣的書店老板
今天，書店老板有一家店打算試營業(yè) customers.length 分鐘。每分鐘都有一些顧客（customers[i]）會進入書店，所有這些顧客都會在那一分鐘結束后離開。
在某些時候，書店老板會生氣。 如果書店老板在第 i 分鐘生氣，那么 grumpy[i] = 1，否則 grumpy[i] = 0。 當書店老板生氣時，那一分鐘的顧客就會不滿意，不生氣則他們是滿意的。
書店老板知道一個秘密技巧，能抑制自己的情緒，可以讓自己連續(xù) X 分鐘不生氣，但卻只能使用一次。
請你返回這一天營業(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.
解題方法
滑動窗口
原址題解
- 解題思路
定義n存儲數(shù)組customers的長度，它與數(shù)組grumpy的長度相等
枚舉遍歷customers
當老板不生氣時，統(tǒng)計顧客滿意的總數(shù)sumC，并把原數(shù)組對應顧客數(shù)清零
當遍歷索引小于[秘密技巧X]時，統(tǒng)計第一組分鐘內顧客滿意的總數(shù)total
遍歷完成后，先認為total就是某一組分鐘內顧客滿意的最大總數(shù)maxTotal
在[X,n)區(qū)間遍歷customers，計算每次移動分鐘后的值total，與maxTotal相比較取最大值
遍歷完成后，感到滿意的最大客戶數(shù)量即為maxTotal+sumC
- 代碼實現(xiàn)
python3
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
n = len(customers)
maxTotal = total = sumC = 0
for i,customer in enumerate(customers):
if grumpy[i]==0:
sumC += customer
customers[i] = 0
elif i<X:
total += customer
maxTotal = total
for i in range(X,n):
total += customers[i]-customers[i-X]
maxTotal = max(maxTotal,total)
return maxTotal+sumC
php
class Solution {
function maxSatisfied($customers, $grumpy, $X) {
$n = count($customers);
$maxTotal = $total = $sumC = 0;
foreach($customers as $i=>$customer){
if($grumpy[$i]==0){
$sum+=$customer;
$customers[$i] = 0;
}elseif($i<$X){
$total+=$customer;
}
}
$maxTotal = $total;
for($i=$X;$i<$n;$i++){
$total += $customers[$i]-$customers[$i-$X];
$maxTotal = max($maxTotal,$total);
}
return $maxTotal+$sum;
}
}
- 文字草稿
customers = [1,0,1,2,1,1,7,5]
grumpy = [0,1,0,1,0,1,0,1]
X = 3
當老板不生氣時，感到滿意的客戶數(shù)量為1+1+1+7=10
使用秘密技巧時，
第1組分鐘內能讓顧客滿意的數(shù)量增加0=0+0+0
第2組分鐘內能讓顧客滿意的數(shù)量增加2=0+0+2
第3組分鐘內能讓顧客滿意的數(shù)量增加2=0+2+0
第4組分鐘內能讓顧客滿意的數(shù)量增加3=2+0+1
第5組分鐘內能讓顧客滿意的數(shù)量增加1=0+0+1
第6組分鐘內能讓顧客滿意的數(shù)量增加6=1+0+5
最終感到滿意的最大客戶數(shù)量為10+6=16
