写点什么

LeetCode 1052. Grumpy Bookstore Owner

用户头像
liu_liu
关注
发布于: 2020 年 07 月 25 日
LeetCode 1052. Grumpy Bookstore Owner

问题描述



今天,书店老板将书店开放 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 <= 20000

  • 0 <= customers[i] <= 1000

  • 0 <= 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;
}



发布于: 2020 年 07 月 25 日阅读数: 47
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 1052. Grumpy Bookstore Owner