Some people choose to see the ugliness in this world. The disarray. I choose to see the beauty.
一些人选择去看见这个世界的丑陋，混乱，我选择去发现美好。
问题描述
今天，书店老板有一家店打算试营业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
窗口内的最大值
数组customers中的每个值表示每分钟内进来的客户量，数组grumpy中的每个值表示每分钟内老板是否生气。
-
如果老板不生气，那么顾客肯定是满意的，我们先计算所有满意的数量。
-
如果老板生气，那么顾客是不满意的，这些不满意的可以构成一个新的数组。而老板可以控制K分钟不生气，这个K分钟我们可以把它当做一个窗口，题目就转化为求这个新的数组中连续K个数字的最大和。
来看下代码
1public int maxSatisfied(int[] customers, int[] grumpy, int X) {
2 int satisfied = 0;//先统计本来就满意的
3 int length = grumpy.length;
4 //新的数组，统计不满意的
5 int[] noSatisfied = new int[length];
6 for (int i = 0; i < length; i++) {
7 if (grumpy[i] == 0)
8 satisfied += customers[i];
9 else
10 noSatisfied[i] = customers[i] * grumpy[i];
11 }
12 //使用两个指针，类似于窗口的左边和右边
13 int left = 0;
14 int right = 0;
15 int max = 0;//记录窗口内的最大值
16 int sum = 0;//记录当前窗口内的值
17 for (; right < length; right++) {
18 sum += noSatisfied[right];
19 //如果窗口长度超过K，要减去窗口左边的值，同时
20 //窗口左边要往右移一步
21 if (right - left >= X) {
22 sum -= noSatisfied[left++];
23 }
24 //保存最大值
25 max = Math.max(max, sum);
26 }
27 //本来就满意的+老板控制情绪让顾客满意的
28 return satisfied + max;
29}
上面计算的时候我们使用了两个for循环，实际上我们还可以把他们合并成一个
1public int maxSatisfied(int[] customers, int[] grumpy, int X) {
2 int satisfied = 0;//本来就满意的
3 int maxPretendSatisfied = 0;//最大抑制情绪满意的
4 int pretendSatisfied = 0;//窗口内抑制情绪满意的
5 for (int i = 0; i < grumpy.length; ++i) {
6 //如果grumpy[i]是0，表示顾客是满意的
7 if (grumpy[i] == 0) {
8 satisfied += customers[i];
9 } else {
10 //如果不等于0，表示顾客是不满意的，但老板可以控制自己的
11 //情绪，顾客表示假装满意
12 pretendSatisfied += customers[i];
13 }
14 //老板控制自己的情绪是有限的，这个范围我们可以把它看做是一个窗口，
15 //这个窗口是一直往右移动的，如果移除窗口的有不满意的，要减去
16 if (i >= X && grumpy[i - X] == 1) {
17 pretendSatisfied -= customers[i - X];
18 }
19 //保存通过抑制情绪使顾客满意的最大数量
20 maxPretendSatisfied = Math.max(maxPretendSatisfied, pretendSatisfied);
21 }
22 //最后返回本来就使顾客满意的数量+抑制情绪使顾客满意的数量
23 return satisfied + maxPretendSatisfied;
24}
总结
顾客本来就满意的只需要累加即可，而顾客不满意的，老板可以通过控制自己的情绪让顾客满意，我们只需要求这连续K个不满意的最大值，问题就很容易解决了。
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有800多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。