问题描述
今天，书店老板将书店开放 customers.length 分钟。每一分钟，会有一定数量的顾客( customers[i] ) 进入书店，然后在一分钟结束时都离开书店。
在某些分钟的时候，老板会变得很暴躁。如果老板在第 i 分钟暴躁，那么记录 grumpy[i] = 1，否则 grumpy[i] = 0。当老板暴躁时，在那一分钟的顾客需求将不能被满足，反之可以。
书店老板有个可以让他们在 X 分钟内不暴躁的秘诀，但是只能被使用一次。
返回今天可以被满足最大顾客的数量。
栗 1：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板可以保持 3 分钟的平静。
原本老板不暴躁的时候，即 grumpy[i] = 0 时，顾客总数为: 1 + 1 + 1 + 7 = 10。
而连续 3 分钟内，老板暴躁时，对应的顾客总数最大为: 1 + 5 = 6。
因此，最大人数为：10 + 6 = 16。
注意：
1 <= X <= customers.length == grumpy.length <= 200000 <= customers[i] <= 10000 <= grumpy[i] <= 1
解题思路
首先我们来分析一下题意。
- 当老板不暴躁时，顾客的需求可以被满足。
- 当老板暴躁时，顾客需求不能被满足。
- 老板可以在连续的 X 分钟内，保持不暴躁。但 X 分钟内，可能会同时包含暴躁和不暴躁的时刻。
显然，老板不暴躁时候的顾客总数是固定的。题目要求返回可以被满足的最大顾客数量。那么问题就转化为：求出在 X 分钟内，老板暴躁时对应的最大顾客总数。
即满足如下等式：
被满足的最大顾客总数 = 不暴躁时的顾客总数 + X 分钟内暴躁时的最大顾客总数。
如何求出 X 分钟内最大的顾客总数呢？看到这里，你可能会想，这还不简单吗？遍历一次，分别求出每 X 分钟对应的顾客数，求出最大值。的确，这是一种方式。
但不知你发现了没，这样会有很多重复计算。
- 第一个 X 分钟的顾客数，
A[0] + ... + A[X-1]。 - 第二个 X 分钟的顾客数，
A[1] + ... + A[X]。
...
它们之间包含重复的部分：A[1] + ... + A[X-1]。当第一次计算过后，后面其实可以省去计算。因此我们可以将其优化，使用增量的方式，在已计算的总和基础上，再加上 A[X] - A[0] 的差值即可。这就是最核心的思想。
具体来说，我们可以预先计算出一个基数总和，即在第一个 X 分钟内老板暴躁时的顾客总数，之后都使用增量计算。
js 代码如下：
/**
* @param {number[]} customers
* @param {number[]} grumpy
* @param {number} X
* @return {number}
*/
var maxSatisfied = function (customers, grumpy, X) {
if (customers && grumpy) {
let i = 0
// x 分钟内暴躁时的顾客总数
let xSum = 0
// x 分钟内暴躁时最大的顾客总数
let maxXSum = 0
// 记录 grumpy = 0 时，客户的总数
let sum = 0
// 首先计算出前 X 个数中 grumpy = 1，对应的客户总数
while (i < X) {
if (grumpy[i] === 1) {
xSum += customers[i]
} else {
sum += customers[i]
}
i += 1
}
// maxXSum 初始值
maxXSum = xSum
while (i < customers.length) {
// 计算不暴躁时的数量
if (grumpy[i] === 0) {
sum += customers[i]
}
const lastIndex = i - X
// 如果不暴躁，则为 0，因为不暴躁有额外的记录。暴躁则为对应的顾客数。
let num = grumpy[i] === 0 ? 0 : customers[i]
let lastNum = grumpy[lastIndex] === 0 ? 0 : customers[lastIndex]
// 计算增量
xSum += num - lastNum
if (maxXSum < xSum) {
maxXSum = xSum
}
i += 1
}
return sum + maxXSum
}
return 0
};
还有一种更简化的写法，是讨论区获赞数最高的答案，但思路是一样的。下面的代码中我添加了一些注释，你可以对照着看。
Java 代码如下：
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
// 不暴躁总数
int satisfied = 0;
// 暴躁最大总数
int maxMakeSatisfied = 0;
// winOfMakeSatisfied 为 x 分钟内的暴躁总数
for (int i = 0, winOfMakeSatisfied = 0; i < grumpy.length; ++i) {
if (grumpy[i] == 0) { satisfied += customers[i]; }
else { winOfMakeSatisfied += customers[i]; }
if (i >= X) {
// 减去差量，更新暴躁时的总量
winOfMakeSatisfied -= grumpy[i - X] * customers[i - X];
}
maxMakeSatisfied = Math.max(winOfMakeSatisfied, maxMakeSatisfied);
}
return satisfied + maxMakeSatisfied;
}
网友评论