当前位置：首页 > news >正文

LeetCode 1052. 爱生气的书店老板【定长滑窗】中等偏低

news 2026/5/12 8:17:00

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

有一个书店老板，他的书店开了n分钟。每分钟都有一些顾客进入这家商店。给定一个长度为n的整数数组customers，其中customers[i]是在第i分钟开始时进入商店的顾客数量，所有这些顾客在第i分钟结束后离开。

在某些分钟内，书店老板会生气。如果书店老板在第i分钟生气，那么grumpy[i] = 1，否则grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续minutes分钟不生气，但却只能使用一次。

请你返回这一天营业下来，最多有多少客户能够感到满意。

示例 1：

输入：customers=[1,0,1,2,1,1,7,5],grumpy=[0,1,0,1,0,1,0,1],minutes=3输出：16解释：书店老板在最后3分钟保持冷静。 感到满意的最大客户数量=1+1+1+1+7+5=16.

示例 2：

输入：customers=[1],grumpy=[0],minutes=1输出：1

提示：

n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 10^4
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1

解法定长滑窗

本题可拆分为两个问题：

老板不生气时的顾客数量之和s 0 s_0s0，这些顾客感到满意。
长度为m i n u t e s minutesminutes的连续子数组中，老板生气时的顾客数量之和s 1 s_1s1的最大值m a x S 1 maxS_1maxS1，这些顾客可以感到满意。

最终答案为s 0 + m a x S 1 s_0 + maxS_1s0+maxS1。第二个问题可用定长滑窗解决。

为什么要分开计算不生气和生气时的顾客？
因为不生气时的顾客可以在窗口外面，需独立计算。

classSolution{publicintmaxSatisfied(int[]customers,int[]grumpy,intminutes){int[]s=newint[2];intmaxS1=0;for(inti=0;i<customers.length;i++){s[grumpy[i]]+=customers[i];intleft=i-minutes+1;// 窗口左端点if(left<0){// 窗口长度不足 minutescontinue;}maxS1=Math.max(maxS1,s[1]);// 窗口最左边元素离开窗口s[1]-=grumpy[left]>0?customers[left]:0;}returns[0]+maxS1;}}

classSolution{public:intmaxSatisfied(vector<int>&customers,vector<int>&grumpy,intminutes){ints[2]{},max_s1=0;for(inti=0;i<customers.size();i++){s[grumpy[i]]+=customers[i];intleft=i-minutes+1;// 窗口左端点if(left<0){// 窗口长度不足 minutescontinue;}max_s1=max(max_s1,s[1]);// 窗口最左边元素离开窗口s[1]-=grumpy[left]?customers[left]:0;}returns[0]+max_s1;}};

classSolution:defmaxSatisfied(self,customers:List[int],grumpy:List[int],minutes:int)->int:s=[0,0]max_s1=0fori,(c,g)inenumerate(zip(customers,grumpy)):s[g]+=c left=i-minutes+1# 窗口左端点ifleft<0:# 窗口长度不足 minutescontinuemax_s1=max(max_s1,s[1])ifgrumpy[left]:s[1]-=customers[left]# 窗口最左边元素离开窗口returns[0]+max_s1

implSolution{pubfnmax_satisfied(customers:Vec<i32>,grumpy:Vec<i32>,minutes:i32)->i32{letk=minutesasusize;letmuts=[0,0];letmutmax_s1=0;for(i,(&c,&g))incustomers.iter().zip(grumpy.iter()).enumerate(){s[gasusize]+=c;ifi<k-1{// 窗口长度不足 minutescontinue;}max_s1=max_s1.max(s[1]);ifgrumpy[i-k+1]==1{s[1]-=customers[i-k+1];// 窗口最左边元素离开窗口}}s[0]+max_s1}}

funcmaxSatisfied(customers[]int,grumpy[]int,minutesint)int{s:=[2]int{}maxS1:=0fori,c:=rangecustomers{s[grumpy[i]]+=c left:=i-minutes+1// 窗口左端点ifleft<0{// 窗口长度不足 minutescontinue}maxS1=max(maxS1,s[1])ifgrumpy[left]>0{s[1]-=customers[left]// 窗口最左边元素离开窗口}}returns[0]+maxS1}

varmaxSatisfied=function(customers,grumpy,minutes){consts=[0,0];letmaxS1=0;for(leti=0;i<customers.length;i++){s[grumpy[i]]+=customers[i];constleft=i-minutes+1;// 窗口左端点if(left<0){// 窗口长度不足 minutescontinue;}maxS1=Math.max(maxS1,s[1]);// 窗口最左边元素离开窗口s[1]-=grumpy[left]?customers[left]:0;}returns[0]+maxS1;};

#defineMAX(a,b)((b)>(a)?(b):(a))intmaxSatisfied(int*customers,intcustomersSize,int*grumpy,intgrumpySize,intminutes){ints[2]={},max_s1=0;for(inti=0;i<customersSize;i++){s[grumpy[i]]+=customers[i];intleft=i-minutes+1;// 窗口左端点if(left<0){// 窗口长度不足 minutescontinue;}max_s1=MAX(max_s1,s[1]);// 窗口最左边元素离开窗口s[1]-=grumpy[left]?customers[left]:0;}returns[0]+max_s1;}