(标签-gru|关键词-数组)

Question

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

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以采用滑动窗口的方法。我们需要遍历整个数组，并且在每次遍历时检查老板是否生气，以及他是否已经使用了抑制情绪的技巧。我们将维护两个变量：satisfied（表示当前窗口内满意客户的数量）和window_sum（表示当前窗口内总的客户数量）。同时，我们还需要一个布尔变量is_cooling_off来跟踪老板是否正在使用冷却技巧。

下面是算法的步骤：

1. 初始化satisfied、window_sum、is_cooling_off和结果变量max_satisfied。
2. 遍历customers和grumpy数组。
3. 对于每个时间点，根据老板的情绪决定是否将当前的顾客计入满意客户数。
4. 将当前时间点的顾客数添加到window_sum中。
5. 检查是否需要应用冷却技巧。如果老板生气并且没有使用过冷却技巧，更新is_cooling_off并从window_sum中减去前minutes个时间点的顾客数。
6. 更新satisfied为window_sum减去当前时间点之前minutes个时间点的顾客数与不满意的顾客数之差。
7. 更新max_satisfied为当前satisfied和已知最大值之间的较大者。
8. 返回max_satisfied作为答案。

以下是实现这个算法的Python代码：

def maxSatisfied(customers, grumpy, minutes):
    window_sum = 0
    satisfied = 0
    is_cooling_off = False
    max_satisfied = 0

    for i in range(len(customers)):
        # Update the current sum of customers
        window_sum += customers[i]

        # If the boss is angry and not cooling off, apply the technique
        if grumpy[i] == 1 and not is_cooling_off:
            is_cooling_off = True
            window_sum -= sum(customers[max(i - minutes, 0):i])

        # Calculate the number of satisfied customers in the current window
        if is_cooling_off:
            satisfied = window_sum
        else:
            satisfied = window_sum - sum(customers[max(i - minutes, 0):i])

        # Update the maximum number of satisfied customers
        max_satisfied = max(max_satisfied, satisfied)

    return max_satisfied

# Example usage
customers = [1, 0, 1, 2, 1, 1, 7, 5]
grumpy = [0, 1, 0, 1, 0, 1, 0, 1]
minutes = 3
print(maxSatisfied(customers, grumpy, minutes))  # Output: 16

这段代码首先初始化了一些变量，然后遍历了customers和grumpy数组，按照上述描述执行操作。在每次循环中，它都会更新满足条件的客户数，并且在适当的时候应用冷却技巧。最后，返回最大的满足条件的客户数。