# 1052. Grumpy Bookstore Owner

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 <= 20000`
• `0 <= customers[i] <= 1000`
• `0 <= grumpy[i] <= 1`

``````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;
}
};
``````

``````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 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation