题目描述
今天,书店老板有一家店打算试营业 customers.length
分钟。每分钟都有一些顾客(customers[i]
)会进入书店,所有这些顾客都会在那一分钟结束后离开。
在某些时候,书店老板会生气。 如果书店老板在第 i
分钟生气,那么 grumpy[i] = 1
,否则 grumpy[i] = 0
。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。
书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X
分钟不生气,但却只能使用一次。
请你返回这一天营业下来,最多有多少客户能够感到满意的数量。
样例
输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出:16
解释:
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16。
注意
1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1
算法
(暴力枚举) $O(n)$
- 统计出不使用技巧能得到满意度的总和
sum
。 - 用一个数组,
sum_grumpy[i]
表示前i
个客户中,生气造成的总不满意度。 - 枚举抑制的时间点,用
sum
累计上sum_grumpy
中一段值来更新答案。
时间复杂度
- 维护数组的时间复杂度为 $O(n)$,枚举答案的时间复杂度也为 $O(n)$,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要额外的数组,故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int n = customers.size(), sum = 0;
vector<int> sum_grumpy(n);
sum_grumpy[0] = grumpy[0] == 1 ? customers[0] : 0;
sum = grumpy[0] == 0 ? customers[0] : 0;
for (int i = 1; i < n; i++) {
sum_grumpy[i] = sum_grumpy[i - 1];
if (grumpy[i] == 1)
sum_grumpy[i] += customers[i];
else
sum += customers[i];
}
int ans = sum_grumpy[X - 1];
for (int i = 1; i < n - X + 1; i++)
ans = max(ans, sum_grumpy[X + i - 1] - sum_grumpy[i - 1]);
return ans + sum;
}
};