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

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

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation