【每日一题】LeetCode 1052.爱生气的书店老板（数组、滑动窗口）

【每日一题】LeetCode 1052.爱生气的书店老板（数组、滑动窗口）

题目描述

书店老板的商店每天有不同数量的顾客进入。每分钟，老板可能或可能不会生气。如果老板生气，那一分钟的顾客就会不满意。老板知道一个秘密技巧，可以让自己在连续的 minutes 分钟内不生气，从而让所有顾客都满意。我们的任务是找出使用这个技巧后，一天中最多有多少顾客能够感到满意。

• customers：一个整数数组，表示每分钟进入商店的顾客数量。
• grumpy：一个整数数组，表示老板每分钟是否生气，1 表示生气，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
• 解释：老板不生气，所有顾客都感到满意。

思路分析

这个问题可以通过滑动窗口的方法来解决。首先，我们计算在没有使用技巧的情况下，顾客感到满意的总数量。然后，我们使用一个滑动窗口来模拟老板使用技巧的情况。窗口的大小是 minutes 分钟，我们计算在这个窗口内，如果老板不生气，顾客的数量。接着，我们移动窗口，每次移动都会更新窗口内的顾客数量，并记录下最大的顾客数量。最后，我们将未使用技巧时的顾客数量与使用技巧时的最大顾客数量相加，得到最终的结果。

代码实现

class Solution {public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {int totalSatisfied = 0; // 记录老板不生气时的总顾客数量int n = customers.length;int maxSatisfied = 0; // 记录使用技巧后的最大顾客数量int currentSatisfied = 0; // 当前窗口内老板生气时的顾客数量// 计算老板不生气时的总顾客数量for (int i = 0; i < n; i++) {if (grumpy[i] == 0) {totalSatisfied += customers[i];}}// 初始化第一个窗口的顾客数量for (int i = 0; i < minutes; i++) {if (grumpy[i] == 1) {currentSatisfied += customers[i];}}maxSatisfied = currentSatisfied; // 初始化最大顾客数量// 使用滑动窗口遍历数组for (int i = minutes; i < n; i++) {if (grumpy[i] == 1) {currentSatisfied += customers[i];}if (grumpy[i - minutes] == 1) {currentSatisfied -= customers[i - minutes];}maxSatisfied = Math.max(maxSatisfied, currentSatisfied);}// 返回最终的最大顾客数量return totalSatisfied + maxSatisfied;}
}