leetcode1052.爱生气的书店老板

leetcode1052.爱生气的书店老板

二月 21, 2020

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.

6ms。首先算出不发动技能的时候，所获得的满意人数。然后再遍历grumpy数组，以x为窗口大小，左边出去对应的操作，和右边进来对应的操作，具体操作在下面的注释里面。

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
28
29
30
31
32
33
34
35
 public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int sum=0,result=0;
        //求出正常情况下不发动能力，这个时候的满意人数。
//        for(int i=0;i<customers.length;i++) {
//        	if(grumpy[i]==0) {
//    			sum+=customers[i];
//    		}       
//    	}
//    	for(int i=0;i<X;i++) {
//    		if(grumpy[i]==1) {
//    			sum+=customers[i];
//    		}    
//    	}这两个for用下面的一个for替换了，但是提交之后反而是7ms，这就很迷惑
    	for(int i=0;i<customers.length;i++) {
    		if(grumpy[i]==0) {
    			sum+=customers[i];
    		}
    		if(i<X&&grumpy[i]==1) {
    			sum+=customers[i];
    		}
    	}
    	result=sum;
    	//最初的窗口状态，这之后窗口右滑，左端出去是0，不变；出去是1，减掉。右端进来，是0，不变；进来是1，加上。
    	for(int i=0;i<customers.length-X;i++) {
    		if(grumpy[i]==1) {
    			sum-=customers[i];
    		}
    		if(grumpy[i+X]==1) {
    			sum+=customers[i+X];
    		}
    		result=Math.max(result,sum);
    	}	
    	return result;	
    }
    //40min

leetcode 5/100