What is the best approach to solve Grumpy Bookstore Owner?

Use a sliding window of size 'minutes' to maximize extra satisfied customers during grumpy periods, adding it to the base satisfaction.

Can I solve this problem without a sliding window?

Brute force is possible but inefficient; the sliding window reduces time complexity from O(n*minutes) to O(n).

How do I handle edge cases like all non-grumpy or all grumpy minutes?

Sum all customers for non-grumpy minutes as base. For all grumpy, apply the sliding window across the entire array to find maximum gain.

Why is this problem categorized under Array and Sliding Window?

Because it requires maintaining a running sum of customers over a consecutive interval within an array, updating efficiently as the window moves.

How do I calculate the total satisfied customers efficiently?

Compute base satisfaction from non-grumpy minutes, then slide a window over grumpy minutes to find maximum additional satisfied customers, summing both for the total.

#1052

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

爱生气的书店老板

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

数组滑动窗口

题目描述

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

在某些分钟内，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[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⁴
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1

lightbulb

解题思路

方法一：滑动窗口

根据题目描述，我们只需要统计老板不生气时的客户数量 $tot$ ，再加上一个大小为 minutes 的滑动窗口中，老板生气时的客户数量的最大值 $mx$ 即可。

我们定义一个变量 $cnt$ 来记录滑动窗口中老板生气时的客户数量，初始值为前 minutes 分钟老板生气时的客户数量。然后我们遍历数组，每次移动滑动窗口时，更新 $cnt$ 的值，同时更新 $mx$ 的值。

最后返回 $tot + mx$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 customers 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxSatisfied(
        self, customers: List[int], grumpy: List[int], minutes: int
    ) -> int:
        mx = cnt = sum(c * g for c, g in zip(customers[:minutes], grumpy))
        for i in range(minutes, len(customers)):
            cnt += customers[i] * grumpy[i]
            cnt -= customers[i - minutes] * grumpy[i - minutes]
            mx = max(mx, cnt)
        return sum(c * (g ^ 1) for c, g in zip(customers, grumpy)) + mx

speed

复杂度分析

指标	值
时间	complexity is O(n) because each minute is visited once for base calculation and once during sliding window. Space complexity is O(1) since calculations are done in-place without extra data structures beyond counters.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Expecting you to recognize that non-grumpy minutes can be counted immediately.
question_mark
Looking for sliding window implementation to optimize consecutive grumpy intervals.
question_mark
Checking if you correctly combine base satisfaction with maximum gain from the window.

warning

常见陷阱

外企场景

error
Forgetting to include base satisfied customers from non-grumpy minutes.
error
Incorrectly summing customers in sliding window due to off-by-one errors.
error
Sliding the window beyond array bounds or miscalculating potential gain.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Varying the length of the grumpy suppression window to see different maximums.
arrow_right_alt
Handling large arrays with maximum customer counts to test O(n) efficiency.
arrow_right_alt
Extending the problem to multiple intervals where grumpiness can be suppressed multiple times.

help

常见问题

外企场景

继续练习

#1040 移动石子直到连续 II #1031 两个无重叠子数组的最大和 #1004 最大连续1的个数 III