Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.
On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.
The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.
Return the maximum number of customers that can be satisfied throughout the day.
Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
Note:
1 <= X <= customers.length == grumpy.length <= 200000 <= customers[i] <= 10000 <= grumpy[i] <= 1
这道题说是有个脾气暴躁的书店老板，一个月总有那么几天暴躁，他一暴躁，顾客的满意度就直线下降。现在给了一个数组 grumpy，说是这个店主在若干分钟内不定时的就会暴躁，对应的时间内书店的客人数量保存在 customers 数组中。但老板有个神奇的方法可以使得自己在连续的X分钟内不暴躁，需要合理使用才能使得更多的顾客满意，让返回最大的满意的顾客数量。首先来想，若这个更年期老板没有这个神奇的方法（太太乐口服液？），那么暴躁的时间就是固定的，则不暴躁时能满足的客人的数量也是确定的，这个可以提前求出来。而使用了神奇配方之后，可以连续X分钟不暴躁，这段时间内原本就不暴躁的区间不会受到影响，即满意的顾客数不会增加。只有这段时间内原本暴躁的分钟内，变的不暴躁了，才会增加满意顾客的数量。为了快速的知道X时间段内暴躁时段的顾客人数，需要建立一个累加数组，只统计暴躁时间段的顾客人数，放到数组 ones 中。同时用一个变量 sum 来统计所有不暴躁时间段的顾客人数，最后只要遍历每个大小为X的窗口，利用 ones 数组来快速得到暴躁时间段的顾客人数，并且加上 sum，用来更新结果 res 即可，参见代码如下：
解法一：
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int n = customers.size(), res = 0, sum = 0;
vector<int> ones(n + 1);
for (int i = 1; i <= n; ++i) {
ones[i] += ones[i - 1];
if (grumpy[i - 1] == 1) {
ones[i] += customers[i - 1];
} else {
sum += customers[i - 1];
}
}
for (int i = 0; i + X <= n; ++i) {
res = max(res, sum + ones[i + X] - ones[i]);
}
return res;
}
};
我们还可以写的更加简洁一下，只用一个 for 循环，这里的 sums 数组就相当于上面的 ones 数组，然后直接把不暴躁时间段的顾客人数加到结果 res 中。在累加 sums 数组的过程中，用当前最后的那个X大小的窗口来更新 mx，最后将 mx 加到结果 res 中并返回即可，参见代码如下：
解法二：
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int res = 0, n = customers.size(), mx = 0;
vector<int> sums(n + 1);
for (int i = 0; i < n; ++i) {
sums[i + 1] = sums[i];
if (grumpy[i] == 0) res += customers[i];
else sums[i + 1] += customers[i];
if (i + 1 - X >= 0) mx = max(mx, sums[i + 1] - sums[i + 1 - X]);
}
return res + mx;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1052
参考资料：
https://leetcode.com/problems/grumpy-bookstore-owner/
https://leetcode.com/problems/grumpy-bookstore-owner/discuss/299237/C%2B%2B-Sliding-Window
https://leetcode.com/problems/grumpy-bookstore-owner/discuss/299230/JavaPython-3-Sliding-window.
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
