[1052][中等][滑动窗口] 爱生气的书店老板

题目描述

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.

提示：

• 1 <= X <= customers.length == grumpy.length <= 20000

• 0 <= customers[i] <= 1000

• 0 <= grumpy[i] <= 1

解题思路

如果老板不能抑制自己的情绪, 那么一天的营业收获的满意量就是不生气的时间对应的客户数量之和. 但有了在一段连续的时间内抑制情绪的能力, 就可以将这段时间内原本要生气气走的客户挽回, 收获额外的满意量.

因此将抑制自己情绪的能力看作一个窗口, 窗口的长度就是可以控制的时间, 问题就转化为了寻找一个最优窗口, 这个窗口对应的生气片段客户总数量最多, 从而能够收获最多的额外满意量.

按索引遍历两个数组, 计算不生气的客户量之和, 统计维护一个窗口, 窗口的尾部为当前遍历到的位置, 统计这个窗口中生气时对应的客户量之和, 同时维护一个全局最大的窗口内生气时客户量之和.

最后的返回就是由基础的不生气总客户量加上抑制能力带来的全局最大额外客户量组成. 对应的代码如下:

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        n = len(customers)
        base, window = 0, 0

        for i in range(X):
            base += customers[i] * (1 - grumpy[i])
            window += customers[i] * grumpy[i]
        max_window = window

        for i in range(X, n):
            base += customers[i] * (1 - grumpy[i])
            window = window + customers[i] * grumpy[i] - customers[i - X] * grumpy[i - X]
            max_window = window if window > max_window else max_window
        return base + max_window