• 题目：1052.爱生气的书店老板
• 难度：中等

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

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

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

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

示例

输入：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分钟不生气时的客户数量总和,这个就是我们下面说的窗口┗|｀O′|┛ 嗷~~
3. 我们开始挪动窗口，将窗口向右挪动一个单位
   1. 窗口减去原窗口的第一个单位
   2. 窗口最加上原窗口的后一个单位
   3. 每次挪动都与窗口旧值比较，取较大值

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
	int total = 0;
    
    //对应步骤1，计算没有生气时所有满意客户数量
	for(int i = 0;i<customers.size();i++){
	if(grumpy[i] == 0){
		total +=customers[i];
		}
	}

    //对应步骤2，计算前X分钟不生气的客户数量总和
	int grow = 0;
	for(int i =0;i<X;i++){
		grow+=customers[i]*grumpy[i];
	}
        
    //对应步骤3，向右挪动窗口
	int max = grow;
	for(int i = X;i<customers.size();i++){
        //对应步骤3.1以及3.2，减去原窗口第一个以及追加原窗口后一个
		grow = grow - customers[i-X]*grumpy[i-X] + customers[i]*grumpy[i];
        //对应步骤3.3，比较以往的最大值，取较大值
		max = std::max(max,grow);
	}

	return max+total;
}