[LeetCode] 1052. Grumpy Bookstore Owner

[grandyang]

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

这道题说是有个脾气暴躁的书店老板，一个月总有那么几天暴躁，他一暴躁，顾客的满意度就直线下降。现在给了一个数组 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 同步地址:

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