爱生气的书店老板(210223)

问题描述

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

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

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

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

提示：

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

示例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的情况下，客户的满意次数，因为有X之后也是在原有基础上对生气的值添加进来;
2. 第二步，我们先找到数组中的第一段X长度的窗口，并记录该窗口中将生气的值累加起来;
3. 接下来，开始将窗口往右移动，每次移动将进入窗口的值判断如果是1生气，则添加到add中，并对移出窗口的值进行判断，如果是1则减去，由此一次滑动之后能得到一个新的add值;
4. 使用maxAdd记录每次滑动窗口的add中的最大值，最后将最大的add值加到总数中返回即可;

答案

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int sum = 0;
        //循环一次获取到没有X的情况下正常获得客户满意次数
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                sum += customers[i];
            }
        }
        //滑动窗口对每一次窗口内的增加数进行记录 并取最大值
        int add = 0;
        //找出第一个窗口的内容
        for (int i = 0; i < X; i++) {
            add += customers[i] * grumpy[i];
        }
        //根据上面条件已经对第一个窗口进行了计算，接下来对整个窗口进行滑动，并增加尾位和去除首位
        int maxAdd = add;
        for (int i = X; i < customers.length; i++) {
            add += customers[i] * grumpy[i];
            add -= customers[i- X] * grumpy[i-X];
            maxAdd = Math.max(add,maxAdd);
        }

        return maxAdd + sum;

    }
}