[Leetcode 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,那么那时候的顾客都不满意，否则满意。因此那个时刻满意的人数是customer[i] * (1-grumpy[i])。同时，给出时间X，老板可以主动控制住在某个连续的X时间段内不grumpy。要求我们求出最大的顾客满意人数。

首先，如果X大于整个时间段，那么老板在任意时刻都是不grumpy的，简单吧所有顾客人数相加就可以。

若X小于整个时间段，我们需要找到某个X时间段：在这一时间段中，能保障老板让最多数量的顾客从不满意转换为满意。因为X是连续的，所以我们可以用sliding window的方法找到这个X对应的最大转换数。最后加上X不存在时，顾客的满意数，就是我们要的答案。

示例代码 (cpp)

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        int total = 0;
        int delta = 0;
        for (auto i = 0; i < customers.size(); ++i) {
            total += customers[i] * (1 - grumpy[i]);
        }
        
        int start = 0;
        int tmpDelta = 0;
        for (auto end = 0; end < customers.size(); end++) {
            tmpDelta += grumpy[end] * customers[end];
            delta = max(delta, tmpDelta);
            if (end - start + 1 == X) {
                tmpDelta -= grumpy[start] * customers[start];
                start++;
            }
        }
        return delta + total;
    }
};

示例代码 (java)

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int satisfied = 0, maxMakeSatisfied = 0;
        for (int i = 0, winOfMakeSatisfied = 0; i < grumpy.length; ++i) {
            if (grumpy[i] == 0) { satisfied += customers[i]; }
            else { winOfMakeSatisfied += customers[i]; }
            if (i >= X) {
                winOfMakeSatisfied -= grumpy[i - X] * customers[i - X];
            }
            maxMakeSatisfied = Math.max(winOfMakeSatisfied, maxMakeSatisfied);
        }
        return satisfied + maxMakeSatisfied;        
    }
}

示例代码 (python)

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        i = win_of_make_satisfied = satisfied = max_make_satisfied = 0
        for c, g in zip(customers, grumpy):
            satisfied += (1 - g) * c
            win_of_make_satisfied += g * c
            if i >= X:
                win_of_make_satisfied -= grumpy[i - X] * customers[i - X]
            max_make_satisfied = max(win_of_make_satisfied, max_make_satisfied)  
            i += 1    
        return satisfied + max_make_satisfied

复杂度分析

时间复杂度: O(n)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！