题目描述
今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。
在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。
书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。
请你返回这一天营业下来,最多有多少客户能够感到满意的数量。
链接:https://leetcode-cn.com/problems/grumpy-bookstore-owner
样例
思路
自己思路:
从左往右滑动X,记录X范围内因生气而走掉的顾客总数,记录最大值。最后用正常情况下应有的值加上刚刚记录的值即可。复杂度O(nx)
官方题解:
思路相近,不过我用了两层循环。官方计算最后添加的值时只用了一层循环,一开始先取前X个元素,然后每次向后移动一格,这样记录最大值。复杂度O(n)
代码
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int i,j;
int total = 0;
int nowmax = -1;
int shijian = customers.length;
if( X >= shijian) {
for(i = 0;i < shijian;i++)
total += customers[i];
return total;
}
for(i = 0;i < shijian;i++)
total += customers[i] * (1 - grumpy[i]);
for(i = 0;i < shijian - X + 1;i++) {
int leave = 0;
for(j = i;j < i + X;j++) {
leave += customers[j] * grumpy[j];
}
nowmax = Math.max(leave,nowmax);
}
return total + nowmax;
}
官方题解
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int total = 0;
int n = customers.length;
for (int i = 0; i < n; i++) {
if (grumpy[i] == 0) {
total += customers[i];
}
}
int increase = 0;
for (int i = 0; i < X; i++) {
increase += customers[i] * grumpy[i];
}
int maxIncrease = increase;
for (int i = X; i < n; i++) {
increase = increase - customers[i - X] * grumpy[i - X] + customers[i] * grumpy[i];
maxIncrease = Math.max(maxIncrease, increase);
}
return total + maxIncrease;
}
}