1052. 爱生气的书店老板

【题目】：1052. 爱生气的书店老板

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int maxAddCount = 0; // 在minutes长度内，还能增加的最大顾客满意人数
        int curAddCount = 0; // 当前窗口内还能增加的顾客满意数
        int curCount = 0; // 原本有的顾客满意数
        int n = customers.size();
        for(int l = 0, r = 0; r < n; ++r) {
            if(grumpy[r] == 1) { // 把老板从生气变成不生气
                curAddCount += customers[r]; 
            }else {
                curCount += customers[r]; // 原有的顾客满意数
            }
            if(r - l + 1 == minutes) {
                maxAddCount = max(maxAddCount, curAddCount);
                if(grumpy[l] == 1) {
                    curAddCount -= customers[l];
                }
                l++;
            }
        }
        return maxAddCount + curCount; // 当天内最大顾客满意数 = 可以增加的最大顾客满意数 + 原本有的顾客满意数
    }
};

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

当天内最大顾客满意数 = 可以增加的最大顾客满意数 + 原本有的顾客满意数
原本有的顾客满意数是动不了的，所以只需要求可以增加的最大顾客满意数。
书店老板可以让自己连续minutes分钟不生气，说明滑动窗口的长度为minutes
所以本题只需要求在minutes的滑动窗口内，可以增加的最大顾客满意数，即在滑动窗口内，可以从grumpy[i]为1变为0后增加的最大顾客满意数。