1052.爱生气的书店老板

曾经终败给现在 2022-11-01 00:54 114阅读 0赞

##### 题目描述： #####

今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers\[i\]）会进入书店，所有这些顾客都会在那一分钟结束后离开。

在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy\[i\] = 1，否则 grumpy\[i\] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。

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

请你返回这一天营业下来，最多有多少客户能够感到满意的数量。

##### 示例 1： #####

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

**提示**

*  1 <= X <= customers.length == grumpy.length <= 20000
 *  0 <= customers\[i\] <= 1000
 *  0 <= grumpy\[i\] <= 1

##### 题解： #####

**思路**

1.  首先，先计算不生气时满意的顾客数量。
2.  滑动窗口的方式，窗口大小为X，计算窗口内最大的顾客数量。
3.  因为生气时 *grumpy\[i\]* 为1，不生气时为0是已经计算了的，所以这里可以用乘法计算数量。
4.  先计算前*X* 项的顾客数量，然后从*X* 项后开始循环，减去*customers\[i-X\]*,加上*customers\[i-X\]* 比较窗口数量的大小。
5.  循环后获得最大的值加上初始的不生气的顾客数量即为最多的满意的顾客数量。

时间复杂度： O(n)

**代码**

/** * @param {number[]} customers * @param {number[]} grumpy * @param {number} X * @return {number} */
    var maxSatisfied = function(customers, grumpy, X) { 
        let initSum = 0, maxSum = 0, addSum = 0
        for(let i = 0; i < customers.length; i ++) { 
            if(grumpy[i] === 0) { 
                initSum += customers[i]
            }
        }
        for(let i = 0; i < X; i++) { 
            addSum += customers[i] * grumpy[i]
        }
        maxSum = addSum
        for(let i = X; i < customers.length; i ++) { 
            addSum = addSum - customers[i - X] * grumpy[i - X] + customers[i] * grumpy[i]
            maxSum = Math.max(maxSum, addSum)
        }
        return initSum + maxSum
    };