题目描述
leetcode 第1052题：爱生气的书店老板
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
解题方法
滑动窗口
原址题解
- 解题思路
定义n存储数组customers的长度，它与数组grumpy的长度相等
枚举遍历customers
当老板不生气时，统计顾客满意的总数sumC，并把原数组对应顾客数清零
当遍历索引小于[秘密技巧X]时，统计第一组分钟内顾客满意的总数total
遍历完成后，先认为total就是某一组分钟内顾客满意的最大总数maxTotal
在[X,n)区间遍历customers，计算每次移动分钟后的值total，与maxTotal相比较取最大值
遍历完成后，感到满意的最大客户数量即为maxTotal+sumC
- 代码实现
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
当老板不生气时，感到满意的客户数量为1+1+1+7=10
使用秘密技巧时，
第1组分钟内能让顾客满意的数量增加0=0+0+0
第2组分钟内能让顾客满意的数量增加2=0+0+2
第3组分钟内能让顾客满意的数量增加2=0+2+0
第4组分钟内能让顾客满意的数量增加3=2+0+1
第5组分钟内能让顾客满意的数量增加1=0+0+1
第6组分钟内能让顾客满意的数量增加6=1+0+5
最终感到满意的最大客户数量为10+6=16
