【2.23】Leetcode每日一题·爱生气的书店老板

2021年02月23日 12时13分

标签： LeetCode 滑动窗口

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

#### 题目来源
来源：力扣（LeetCode）

链接：[题目链接](https://leetcode-cn.com/problems/grumpy-bookstore-owner "题目链接")

## 解题思路
从“连续X分钟不生气”可以得知题目需要使用滑动窗口求解。

首先让窗口处于`customer`数组的开头，统计最开始`X`分钟老板不生气时，客户能够感到满意的数量。然后将窗口后移一个位置，此时原窗口的第一个位置老板的状态需要重新计算，并且现窗口的最后一个位置老板的状态也需要重新计算。最后取最大值即可。

## 代码
````cpp
class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        const int N = customers.size();
        int res = 0, i, j, temp = 0;
        for(i = 0; i < X; i++){
            res += customers[i] * (1-(grumpy[i]&0));
        }
        for(i = X; i < N; i++){
            res += customers[i] * (1-grumpy[i]);
        }
        i = 0, j = X;
        temp = res;
        while(j < N){
            temp = temp - customers[i] * (1-(grumpy[i]&0)) + customers[i] * (1-grumpy[i]);
            temp = temp - customers[j] * (1-grumpy[j]) + customers[j] * (1-(grumpy[j]&0));
            res = max(res, temp);
            i++;
            j++;
        }
        return res;
    }
};
````
## 用时和内存
> 执行用时：32 ms, 在所有 C++ 提交中击败了93.53%的用户
> 内存消耗：29.3 MB, 在所有 C++ 提交中击败了71.21%的用户

所有评论

166****5019 2021年02月24日 13:21:24
沙发

参与主题/评论回复

166****5019 发表于2021年02月24日 13:21:24
沙发

回复评论

邮箱

图形验证码

邮箱验证码
- 166****5019 2021年02月24日 13:21:56
  借楼
  
  参与主题/评论回复
  
  166****5019 发表于2021年02月24日 13:21:56
  借楼
  
  回复评论
  
  邮箱
  
  图形验证码
  
  邮箱验证码
- 166****5019 2021年02月24日 15:36:25
  写得不错
  
  参与主题/评论回复
  
  166****5019 发表于2021年02月24日 15:36:25
  写得不错
  
  回复评论
  
  邮箱
  
  图形验证码
  
  邮箱验证码
  - 166****5019 2021年02月27日 21:13:23
    好
    
    参与主题/评论回复
    
    166****5019 发表于2021年02月27日 21:13:23
    好
    
    回复评论
    
    邮箱
    
    图形验证码
    
    邮箱验证码
    
    166****5019 2021年02月27日 21:13:55
    123
    
    参与主题/评论回复
    
    166****5019 发表于2021年02月27日 21:13:55
    123
    
    回复评论
    
    邮箱
    
    图形验证码
    
    邮箱验证码
    
    166****5019 2021年02月27日 21:47:52
    测试回复中的验证码
    
    参与主题/评论回复
    
    166****5019 发表于2021年02月27日 21:47:52
    测试回复中的验证码
    
    回复评论
    
    邮箱
    
    图形验证码
    
    邮箱验证码
    
    914*********.com 2024年03月25日 00:09:57
    沙发
    
    参与主题/评论回复
    
    914*********.com 发表于2024年03月25日 00:09:57
    沙发
    
    回复评论
    
    邮箱
    
    图形验证码
    
    邮箱验证码
914*********.com 2024年03月25日 00:08:31
123

参与主题/评论回复

914*********.com 发表于2024年03月25日 00:08:31
123

回复评论

邮箱

图形验证码

邮箱验证码
vis***********.com 2024年04月24日 21:07:08
测试

参与主题/评论回复

vis***********.com 发表于2024年04月24日 21:07:08
测试

回复评论

邮箱

图形验证码

邮箱验证码

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2.23】Leetcode每日一题·爱生气的书店老板

所有评论

新增评论