解决方案

分析

推理

板蓝根的效果

板蓝根能让 原本因为店长 心情不好 而变得 心情好，导致 客户 不开心 而变得 开心，从而增加开心的客户数量

板蓝根不能达到的效果

服用板蓝根 不能让 原本店长开心的那几分钟 的开心的顾客 更开心，也就是没效果。

思路

计算出来 原本 店长心情好的那几分钟，有多少顾客本身就开心 $n_{Base}$

找出 店长心情不好的那几分钟，所影响的顾客数据

从这些被影响的数据中，找到 连续 X 元素的最大值，即 增益的最大值 $n_{MaxGain}$

从而得到整体 最多开心人数的 最大值 $max$

$max = n_{Base} + n_{MaxGain}$

Java 代码

Runtime: 2 ms

Memory Usage: 40.5 MB

Beats 100.00% of java submissions.

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 36 37 38 39 40 
public class Solution {    public int maxSatisfied(int[] customers, int[] grumpy, int X) {         // 1. 计算原本就开心的客户数量 n base        int baseCount = 0;        for (int i = 0; i < customers.length; i++) {            if (grumpy[i] == 0) {                baseCount += customers[i];            }        }         // 2. 生成 不开心客户的数组        int[] sadCustomers = new int[customers.length];        for (int i = 0; i < customers.length; i++) {            if (grumpy[i] == 1) {                sadCustomers[i] = customers[i];            }        }         // 3. 计算 X 分钟板蓝根 所带来的最大收益        // 3.1 先计算 前 X 分钟的收益        int gain = 0;        for (int i = 0; i < X; i++) {            gain += sadCustomers[i];        }         // 3.2 采用 改变量 计算接下来每个区间的 收益并 记录最大值        int maxGain = gain;        for (int i = X; i < sadCustomers.length; i++) {            gain += sadCustomers[i];            gain -= sadCustomers[i - X];            if (gain > maxGain) {                maxGain = gain;            }        }         // 4. 求和        return baseCount + maxGain;    }}

Java Script 代码

Runtime: 56 ms

Memory Usage: 37.9 MB

Beats 99.20% of javascript submissions.

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 
var maxSatisfied = function(customers, grumpy, X) {    // 1. 计算原本就开心的客户数量 n base    let baseCount = 0;    for (let i = 0; i < customers.length; i++) {        if (grumpy[i] === 0) {            baseCount += customers[i];        }    }     // 2. 生成 不开心客户的数组    const sadCustomers = customers.map((customer, i) => {        return grumpy[i] === 1 ? customer : 0;    })     // 3. 计算 X 分钟板蓝根 所带来的最大收益    // 3.1 先计算 前 X 分钟的收益    let gain = 0;    for (let i = 0; i < X; i++) {        gain += sadCustomers[i];      }     // 3.2 采用 改变量 计算接下来每个区间的 收益并 记录最大值    let maxGain = gain;    for (let i = X; i < sadCustomers.length; i++) {        gain += sadCustomers[i];        gain -= sadCustomers[i - X];        if (gain > maxGain) {            maxGain = gain;        }    }     return baseCount + maxGain;};

Python 代码

Runtime: 76 ms

Memory Usage: 14.9 MB

Beats 85.65% of python submissions.

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 
class Solution:    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:         # 1. 计算原本就开心的客户数量 n base        base_count = 0        for i in range(len(customers)):            if (grumpy[i] == 0):                base_count += customers[i]         # 2. 生成 不开心客户的数组        sad_customers = []        for i in range(len(customers)):            sad_customers.append(customers[i] if grumpy[i] == 1 else 0)         # 3. 计算 X 分钟板蓝根 所带来的最大收益        # 3.1 先计算 前 X 分钟的收益        gain = sum(sad_customers[:X])         # 3.2 采用 改变量 计算接下来每个区间的 收益并 记录最大值        max_gain = gain        for i in range(X, len(sad_customers)):            gain += sad_customers[i]            gain -= sad_customers[i - X]            if gain > max_gain:                max_gain = gain         # 4. 求和        return base_count + max_gain