题目描述

今天，书店老板有一家店打算试营业 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

样例

输入：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段时间里，我们去找最大值。当时这复杂度太高，要TL.我还是把代码贴在下面.

2. 滑动窗口
定义两个指针 i,j;
总体思路是一样的，先求不生气，答案累加求和。我们要在代码中把不生气的顾客的人数==0,不然后面会影响结果。
我们从前向后遍历，滑动窗口的大小是X，当超出这个范围,左边i的指针减去当前这个值，并++。直到遍历完循环，得到答案

C++ 暴力代码

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        int n = grumpy.size();
        int res = 0;
        for (int i = 0;i < n;i ++){
            if (grumpy[i] == 0) res += customers[i];
        }
        int ans = 0;
        bool flag = true;// 优化
        for (int i = 0;i < n;i ++){ 
           int cnt = X,temp = 0; 
           int j = i;
            while(cnt --){//这里其实最坏的情况n * x;
                if (j < n && grumpy[j ] == 1) temp += customers[j];
                if (j >= n) { break;  flag = false;}
                j ++;
            }
            if (!flag) break;
            ans = max(ans,temp);
        }
        return (ans + res);
    }
};

C++ 优化代码

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        int n = grumpy.size();
        int res = 0;
        for (int i = 0;i < n;i ++){
            if (grumpy[i] == 0){
                res += customers[i];
                customers[i] = 0; //这里的作用就是在滑动窗口的时候，不会影响答案。
            }
        }
        int cur = 0 ,mmax = 0;
        for (int i = 0,j = 0;i < n;i ++){
            cur += customers[i];//累加答案
            if (i - j + 1 > X) cur -= customers[j++];
            mmax = max(mmax,cur);
        }
        return (mmax + res);
    }
};
/*
处理连续区间的时候，一个区间的元素只有两种可能，我们想得到一种的答案，我们目前有两种解法
1.if判断
2.把另一种情况全部置为0,遍历相加
*/