【滑动窗口】LeetCode 1052. 爱生气的书店老板

1052. 爱生气的书店老板

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/grumpy-bookstore-owner/

题目

今天，书店老板有一家店打算试营业 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.

提示：

• 1 <= X <= customers.length == grumpy.length <= 20000
• 0 <= customers[i] <= 1000
• 0 <= grumpy[i] <= 1

解题思路

思路：滑动窗口

先审题，题目给定的数组 $customers$，其中：

• 数组长度 $len(customers)$ 表示书店老板试营业的时间（单位：分钟）；
• 数组中的每个元素 $customers[i]$ 表示每分钟到店的顾客数。

其中，顾客从进店到离开的时间为一分钟，即是说，每分钟到店的顾客，一分钟结束后都会离开，而下一批顾客会进店。

现在题目中说明，书店的老板有个怪脾气，会在某些时候生气，只要老板生气，此时在店中的顾客就会不满意，否则顾客是满意的。

这里由数组 $grumpy$ 表示老板当前时间是否是生气的状态，其中：

• 元素值为 1 时，表示老板生气；
• 元素值为 0 时，表示老板不生气。

而现在又知道，老板有个【秘密技巧】，能够抑制自己的情绪，让自己连续 $X$ 分钟不会生气，但是只能使用一次。

最后，题目要求一天营业下来，最多能够使多少顾客满意？

根据上面的描述，可以分为两部分来看：

• 正常情况下（即是不使用技巧），老板会生气，此时顾客会不满意，反之则满意；

• 但老板能够使用【秘密技巧】，此时这段时间能够防止顾客不满意的情况出现，起到挽留的效果。

文中提及的 挽留，此篇题解均表使顾客满意。

因为明确知道使用【秘密技巧】，能够连续 $X$ 分钟不生气，那么这里可以使用滑动窗口的技巧来解决本题，具体的思路如下：

• 首先考虑正常情况下（不使用技巧）时，满意顾客的数量 $total$；
• 接着考虑老板使用 秘密技巧 时能够挽留的最大顾客数 $max\_increase$，具体的方法：
  • 定义一个长度为 $X$ 的窗口（表示使用技巧的这段时间），先计算窗口中能够挽留顾客的数量 $increase$；
  • 移动窗口，此时窗口内会有元素离开及新元素被纳入。若离开元素为不满意的顾客，那么减少相应的顾客数，否则不处理。若纳入的新元素为不满意的顾客，这部分会被挽留，那么需要增加相应的顾客数。
• 最终，窗口移动到末尾时，$total$ 与 $max\_increase$ 的和即是最多能使顾客满意的数量。

以题目示例，用图示的方式展示下效果，如下：

具体的代码实现如下。

class Solution:def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:total = 0n = len(customers)# n = len(grumpy)# 先考虑老板不使用秘密技巧的情况for i in range(n):if grumpy[i] == 0:total += customers[i]# 使用滑动窗口的技巧# 窗口从数组头部开始，先计算当前窗口能挽留的顾客数increase = 0for i in range(X):# 窗口表示老板使用秘密技巧的一段时间# 此时，老板不会生气，那么原本因老板生气的顾客将不会不满意if grumpy[i] == 1:increase += customers[i]# 记录窗口移动，能挽留的最大顾客数max_increase = increase# 窗口进行移动for i in range(X, n):# 若离开窗口的是不满意的顾客，那么原本挽留的顾客数将相应减少if grumpy[i - X] == 1:increase -= customers[i - X]# 若进入窗口的是不满意的顾客，那么挽留的顾客相应增加if grumpy[i] == 1:increase += customers[i]max_increase = max(increase, max_increase)return total + max_increase

复杂度分析

• 时间复杂度：$O(n)$，$n$ 为数组 $customers$ 和 $grumpy$ 的长度。
• 空间复杂度：$O(1)$

欢迎关注

公众号 【书所集录】

如有错误，烦请指出，欢迎指点交流。若觉得写得还不错，麻烦点个赞👍，谢谢。