建材网站建设哪家,动漫设计与制作学费,餐饮网站开发方案,如何网站建设网站【每日一题】LeetCode 1052.爱生气的书店老板#xff08;数组、滑动窗口#xff09;
题目描述
书店老板的商店每天有不同数量的顾客进入。每分钟#xff0c;老板可能或可能不会生气。如果老板生气#xff0c;那一分钟的顾客就会不满意。老板知道一个秘密技巧#xff0c;…【每日一题】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;}
}
