Medium

题目描述

有一个书店老板，他的书店开放了 n 分钟。给你一个长度为 n 的整数数组 customers，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客都会在第 i 分钟结束后离开。

在某些时候，书店老板会生气。给你一个长度为 n 的二进制数组 grumpy，其中如果 grumpy[i] 为 1，则表示老板在第 i 分钟时生气，为 0 则表示不生气。

当书店老板生气时，那一分钟进入的顾客就会不满意，否则他们是满意的。

书店老板知道一个秘密技巧，能保持 minutes 分钟不生气，但这个技巧只能使用一次。

返回一整天中最多有多少客户能够感到满意。

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持不生气。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

示例 2：

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

提示：

  • n == customers.length == grumpy.length
  • 1 <= minutes <= n <= 2 * 10^4
  • 0 <= customers[i] <= 1000
  • grumpy[i] 是 0 或 1

解题思路

这是一个典型的滑动窗口问题。我们需要找到一个长度为 minutes 的连续时间段，在这个时间段内使用秘密技巧让老板保持不生气，使得总的满意顾客数最大。

解题思路分为两步：

  1. 计算基础满意顾客数：遍历整个数组，统计所有老板不生气时刻的顾客数量，这些顾客无论如何都会满意。

  2. 使用滑动窗口找到最佳时间段：

    • 维护一个长度为 minutes 的滑动窗口
    • 对于窗口内每个时刻，如果老板原本生气（grumpy[i] = 1），那么使用技巧后可以额外获得 customers[i] 个满意顾客
    • 滑动窗口，找到能够额外获得最多满意顾客的时间段

具体实现时，先计算第一个窗口能额外获得的满意顾客数，然后滑动窗口：每次向右移动时，去掉左边界的贡献，加上新右边界的贡献。

最终答案 = 基础满意顾客数 + 最大额外满意顾客数。

时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int n = customers.size();
        
        // 计算基础满意顾客数（老板不生气时的顾客）
        int baseSatisfied = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                baseSatisfied += customers[i];
            }
        }
        
        // 计算第一个窗口内能额外获得的满意顾客数
        int extraSatisfied = 0;
        for (int i = 0; i < minutes; i++) {
            if (grumpy[i] == 1) {
                extraSatisfied += customers[i];
            }
        }
        
        // 滑动窗口找到最大额外满意顾客数
        int maxExtraSatisfied = extraSatisfied;
        for (int i = minutes; i < n; i++) {
            // 移除窗口左边界的贡献
            if (grumpy[i - minutes] == 1) {
                extraSatisfied -= customers[i - minutes];
            }
            // 添加新的右边界贡献
            if (grumpy[i] == 1) {
                extraSatisfied += customers[i];
            }
            maxExtraSatisfied = max(maxExtraSatisfied, extraSatisfied);
        }
        
        return baseSatisfied + maxExtraSatisfied;
    }
};

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        
        # 计算基础满意顾客数（老板不生气时的顾客）
        base_satisfied = sum(customers[i] for i in range(n) if grumpy[i] == 0)
        
        # 计算第一个窗口内能额外获得的满意顾客数
        extra_satisfied = sum(customers[i] for i in range(minutes) if grumpy[i] == 1)
        
        # 滑动窗口找到最大额外满意顾客数
        max_extra_satisfied = extra_satisfied
        for i in range(minutes, n):
            # 移除窗口左边界的贡献
            if grumpy[i - minutes] == 1:
                extra_satisfied -= customers[i - minutes]
            # 添加新的右边界贡献
            if grumpy[i] == 1:
                extra_satisfied += customers[i]
            max_extra_satisfied = max(max_extra_satisfied, extra_satisfied)
        
        return base_satisfied + max_extra_satisfied

public class Solution {
    public int MaxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int n = customers.Length;
        
        // 计算基础满意顾客数（老板不生气时的顾客）
        int baseSatisfied = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                baseSatisfied += customers[i];
            }
        }
        
        // 计算第一个窗口内能额外获得的满意顾客数
        int extraSatisfied = 0;
        for (int i = 0; i < minutes; i++) {
            if (grumpy[i] == 1) {
                extraSatisfied += customers[i];
            }
        }
        
        // 滑动窗口找到最大额外满意顾客数
        int maxExtraSatisfied = extraSatisfied;
        for (int i = minutes; i < n; i++) {
            // 移除窗口左边界的贡献
            if (grumpy[i - minutes] == 1) {
                extraSatisfied -= customers[i - minutes];
            }
            // 添加新的右边界贡献
            if (grumpy[i] == 1) {
                extraSatisfied += customers[i];
            }
            maxExtraSatisfied = Math.Max(maxExtraSatisfied, extraSatisfied);
        }
        
        return baseSatisfied + maxExtraSatisfied;
    }
}

var maxSatisfied = function(customers, grumpy, minutes) {
    const n = customers.length;
    
    // 计算基础满意顾客数（老板不生气时的顾客）
    let baseSatisfied = 0;
    for (let i = 0; i < n; i++) {
        if (grumpy[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组两次，一次计算基础满意顾客数，一次滑动窗口
空间复杂度O(1)只使用常数额外空间