爱生气的书店老板

难度: Medium

有一个书店老板，他的书店开了 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⁴
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1

Submission

运行时间: 39 ms

内存: 17.6 MB

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        max_sum, sums, max_start = 0, 0, 0
        start = 0
        for end in range(len(customers)):
            if grumpy[end] == 1:
                sums += customers[end]
            # 找到最大的数量
            if sums > max_sum:
                max_sum = sums
                max_start = start
            if end >= minutes - 1:
                if grumpy[start]:
                    sums -= customers[start]
                start += 1
        for i in range(max_start, max_start + minutes):
            if grumpy[i] == 1:
                grumpy[i] = 0
        res = 0
        for i in range(len(customers)):
            if grumpy[i] == 0:
                res += customers[i]
        return res

Explain

该题解采用了滑动窗口的方法来解决问题。首先，通过一个滑动窗口来找出如果书店老板连续不生气持续 `minutes` 分钟时，可以使得最多的顾客满意的区间。在这个过程中，我们维护一个窗口，窗口大小为 `minutes`，窗口内包括了因为老板生气而导致的不满意的顾客数量。接着，我们遍历整个 `customers` 数组，调整 `grumpy` 数组，使得在选定的 `minutes` 分钟内，老板不生气（即将 `grumpy` 对应位置置为0）。最后，重新计算整个数组中满意顾客的总数。通过这种方式，我们可以得到最大的满意顾客数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        max_sum, sums, max_start = 0, 0, 0 # 初始化最大不满意顾客数、当前窗口不满意顾客数和最大窗口起始位置
        start = 0 # 滑动窗口的起始位置
        for end in range(len(customers)): # 遍历每个分钟
            if grumpy[end] == 1: # 如果老板这一分钟生气
                sums += customers[end] # 增加这一分钟的顾客数到当前不满意顾客总数
            # 更新最大不满意顾客数和窗口起始位置
            if sums > max_sum:
                max_sum = sums
                max_start = start
            if end >= minutes - 1: # 窗口大小达到minutes时，开始滑动窗口
                if grumpy[start]: # 如果窗口起始分钟老板生气，则减去那一分钟的顾客数
                    sums -= customers[start]
                start += 1 # 窗口滑动
        for i in range(max_start, max_start + minutes): # 将选定的minutes分钟内老板的状态改为不生气
            if grumpy[i] == 1:
                grumpy[i] = 0
        res = 0 # 重新计算满意的顾客总数
        for i in range(len(customers)):
            if grumpy[i] == 0: # 如果老板不生气，顾客满意
                res += customers[i]
        return res

Explore

在这个问题中，关键在于最大化在书店老板不生气的时间段内顾客的满意度。由于老板生气时顾客不满意，这些分钟造成的不满意顾客数量是可以通过使用老板不生气的技巧来避免的。因此，通过累加只在老板生气时的顾客数，我们可以找到如果老板连续不生气一段时间（minutes分钟），可以转变最多的不满意顾客为满意顾客的时间段。这是一个优化问题，通过滑动窗口来寻找这样的最优时间段，使得转变效果最大。

算法在这种情况下表现是稳定的。滑动窗口算法设计之初就考虑到了边界情况，窗口可以从数组的开始处滑动到结束处。当窗口开始或结束在数组的边界时，算法依然正确地处理了窗口内的顾客数累加和窗口外的顾客数减去，保证了在任何情况下都能找到最优的连续 `minutes` 分钟使得最多的顾客满意。

算法首先通过滑动窗口找到了使得最多顾客满意的最优连续 `minutes` 分钟（最大不满意顾客数的窗口）。一旦这个窗口确定后，我们在这个窗口范围内将 `grumpy` 数组对应的值从1改为0，表示在这个时段老板不生气。这个修改是在整个算法过程中唯一一次对 `grumpy` 数组的修改，确保了老板的不生气技巧只被使用一次。

虽然滑动窗口帮助我们确定了最优的 `minutes` 分钟使得最多顾客由不满变为满意，但窗口操作只是帮助我们确定了这个时间段，并没有计算这一操作后整个数组中的总满意顾客数。因此，需要在修改了 `grumpy` 数组后，重新遍历 `customers` 数组，根据现在的 `grumpy` 状态统计总的满意顾客数。这是因为数组中的其他部分也可能有顾客在老板不生气时已经满意，这部分顾客在滑动窗口操作中没有被计算。