LeetCode--1052.爱生气的书店老板
Skyen Lv4
 2021-02-23 16:25:45    

Description

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

Solution

  • 先求出老板不生气时候的顾客总数 然后遍历一次customer，i < X就是刚开始取前 X 个大小的窗口先计算，然后接下来每次移动一个单位
  • 每次窗口的计算可以基于上一个窗口的结果来计算 窗口右移，左边窗口出去一个元素，右边窗口进入一个元素
  • 对于出窗口的元素，我们要判断在此时老板是否生气grumpy[i-X] == 1，因为只有生气的话，我们出窗口时候才需要减去他，如果不生气的话，就不用减去了
  • 对于进入窗口的元素，我们也要判断是否老板生气grumpy[i] == 1，只有生气我们才需要加上此时的顾客temp += customers[i]; 最后的结果就是所有窗口中最大值的那个
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
class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X){
        int time = customers.size();
        int count = 0,max = 0;
        for(int i=0;i<time;i++){
            if(grumpy[i]==0){  
                count += customers[i];
            }
        }
        max = count;
        for(int i=0;i<time;i++){
            if(i<X){
                if(grumpy[i]==1){
                    count += customers[i];
                }
            }else{
                if(grumpy[i-X]==1){
                    count -= customers[i-X];
                }
                if(grumpy[i]==1){
                    count += customers[i];
                }
            }
            if(max<count)  max=count;    
        }
        return max;

    }
};