LC1052. 爱生气的书店老板

题目描述

有一个书店老板，他的书店开了 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

题目解析

好的，没问题！我们一起来把这道题彻底搞懂。

题目在说什么

想象一下，你是一个书店老板，你的书店营业了 n 分钟。每分钟都会有一批顾客进来，比如第 0 分钟来了 customers[0] 个人，第 1 分钟来了 customers[1] 个人…… 这些顾客会在这一分钟结束的时候离开。

但是，你这个老板有个坏毛病：有时候会生气。你生气的时候（grumpy[i] = 1），那一分钟进来的顾客就会觉得服务不好，不满意地走了。你不生气的时候（grumpy[i] = 0），顾客就很满意。

不过，你有一个秘密技巧：你可以让自己连续 minutes 分钟不生气，但这个技巧只能用一次。

现在问题来了：你最多能让多少位顾客感到满意？

我们来看题目给的例子：

customers = [1, 0, 1, 2, 1, 1, 7, 5]
grumpy =    [0, 1, 0, 1, 0, 1, 0, 1]
minutes = 3

• 第 0 分钟：来了 1 人，老板不生气 (0)，这 1 人满意。
• 第 1 分钟：来了 0 人，老板生气 (1)，没人来，无所谓。
• 第 2 分钟：来了 1 人，老板不生气 (0)，这 1 人满意。
• 第 3 分钟：来了 2 人，老板生气 (1)，这 2 人不满意。
• 第 4 分钟：来了 1 人，老板不生气 (0)，这 1 人满意。
• 第 5 分钟：来了 1 人，老板生气 (1)，这 1 人不满意。
• 第 6 分钟：来了 7 人，老板不生气 (0)，这 7 人满意。
• 第 7 分钟：来了 5 人，老板生气 (1)，这 5 人不满意。

如果不使用技巧，满意的顾客是：第0、2、4、6分钟的人，一共 1 + 1 + 1 + 7 = 10 人。

但我们可以用一次技巧，让自己连续 3 分钟不生气。我们选哪 3 分钟呢？题目说选最后 3 分钟（第 5、6、7 分钟），但注意，第 6 分钟本来就不生气，所以技巧主要影响的是第 5 和第 7 分钟。原本第 5 分钟（生气）的 1 人，和第 7 分钟（生气）的 5 人，现在都变得满意了。再加上本来就满意的那些人，结果就是 10 + 1 + 5 = 16 人。这就是最优解。

思路是怎么来的

这道题的核心是：我们只能选一个连续的 `minutes` 分钟区间，让这个区间内的所有顾客都变得满意（不管老板原本生不生气）。

那么，我们怎么找到这个最好的区间呢？

一个最直接的想法是：把所有可能的连续 minutes 分钟的区间都试一遍，看看哪个区间能“额外”让最多的顾客满意。

比如，minutes = 3，可能的区间有：

• 区间 [0, 1, 2]：这 3 分钟里，原本有多少顾客因为老板生气而不满意？我们看看 grumpy 数组，第 0 分钟不生气，第 1 分钟生气，第 2 分钟不生气。所以，这个区间能“挽救”的顾客只有第 1 分钟的 0 人（因为没人来）。
• 区间 [1, 2, 3]：第 1 分钟生气（0人），第 2 分钟不生气，第 3 分钟生气（2人）。能挽救 0 + 2 = 2 人。
• 区间 [2, 3, 4]：第 2 分钟不生气，第 3 分钟生气（2人），第 4 分钟不生气。能挽救 2 人。
• 区间 [3, 4, 5]：第 3 分钟生气（2人），第 4 分钟不生气，第 5 分钟生气（1人）。能挽救 2 + 1 = 3 人。
• 区间 [4, 5, 6]：第 4 分钟不生气，第 5 分钟生气（1人），第 6 分钟不生气。能挽救 1 人。
• 区间 [5, 6, 7]：第 5 分钟生气（1人），第 6 分钟不生气，第 7 分钟生气（5人）。能挽救 1 + 5 = 6 人。

你看，区间 [5, 6, 7] 能挽救 6 人，是最多的。所以，我们就在这个区间使用技巧，最终满意的顾客 = 原本就满意的顾客 (10人) + 这个区间挽救的顾客 (6人) = 16人。

这个“把所有区间都试一遍”的方法，我们称之为滑动窗口。想象一个长度为 minutes 的窗口，从数组开头滑到结尾，我们每滑动一次，就计算一下窗口内能挽救多少顾客，然后记录下最大值。

代码逐步拆解

我们来看代码怎么写。我会用 Python 来写，思路和 C++/Java 是一样的。

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        
        # 第一步：计算原本就满意的顾客总数
        total_satisfied = 0
        for i in range(n):
            if grumpy[i] == 0:
                total_satisfied += customers[i]
        
        # 第二步：初始化滑动窗口
        # 先计算第一个窗口（[0, minutes-1]）内，能挽救的顾客数
        extra_customers = 0
        for i in range(minutes):
            if grumpy[i] == 1:
                extra_customers += customers[i]