1052. The Angry Bookstore Boss

1052. 爱生气的书店老板

#滑动窗口
有一个书店老板,他的书店开了 n 分钟.每分钟都有一些顾客进入这家商店.给定一个长度为 n 的整数数组 customers ,其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量,所有这些顾客在第 i 分钟结束后离开.

在某些时候,书店老板会生气. 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0.

当书店老板生气时,那一分钟的顾客就会不满意,若boss is not angry则顾客是满意的.

书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 minutes 分钟不生气,但却只能使用一次.

请你返回 这一天营业下来,最多有多少客户能够感到满意 .

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静.
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
示例 2：

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

提示：

n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 104
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/grumpy-bookstore-owner

解法：滑动窗口

class Solution {
    
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
    
        // When the boss has no skills,The number of satisfied customers
        int n = 0;
        int length = customers.length;

        for (int i = 0; i < length; i++) {
    
            int p = customers[i];
            // boss is not angry
            if (grumpy[i] == 0) {
    
                n += p;
            }
            // The boss activates the skill right from the start,比如 minutes 是 3,那么 0 1 2 Customers in minutes will be satisfied（Because the boss used skills,不会生气）
            if (i < minutes && grumpy[i] == 1) {
    
                n += p;
            }
        }
        // max is the maximum number of customers that can be satisfied,The initial value is that the boss activates the skill at the beginning
        int max = n;
        // 滑动窗口,From the first activation of the skill to the end
        for (int i = minutes; i < length; i++) {
    
            // Each length is  minutes Each time the sliding window is moved to the right,The minute the far left slides out of the window,If the boss is angry,Just subtract the number of customers that minute from the number of satisfied customers.

            // Slide in from the window
            if (grumpy[i] == 1) {
    
                n += customers[i];
            }
            // Slide out of the window
            if (grumpy[i - minutes] == 1) {
    
                n -= customers[i - minutes];
            }
            max = n > max ? n : max;
        }
        return max;
    }
}

作者：xiu-qiang-jiang
链接：https://leetcode.cn/problems/grumpy-bookstore-owner/solution/by-xiu-qiang-jiang-foid/