LeetCode 1052. 爱生气的书店老板
目录
题目描述
题意分析
书店按分钟记录进店人数
customers[i]，grumpy[i]标记老板这一分钟是否生气：不生气（0）则这批顾客满意，生气（1）则不满意。老板有一次「保持冷静」的技能，可以让连续minutes分钟内不生气，只能用一次。求最多能有多少顾客满意。关键在于把答案拆成两部分。老板本来就不生气的那些分钟，顾客无论如何都满意，这部分是与决策无关的常量；技能只能改变生气的分钟，而且只对技能窗口覆盖到的生气分钟起作用。所以
答案 = 基础满意人数 + 窗口内被挽回的人数，前者固定，后者要最大化。「连续
minutes分钟」且「只能用一次」这两条合起来，说明待优化的对象是一个长度固定的滑动区间——不是可变长度的窗口，也不是多段区间。固定长度是个很强的信号：窗口右移一格，只需要减去移出的元素、加上移入的元素，不必重新求和。约束是
1 ≤ minutes ≤ customers.length ≤ 2 × 10^4，0 ≤ customers[i] ≤ 1000。规模决定了 $O(n \cdot minutes)$（最坏 $4 \times 10^8$）会超时，必须做到 $O(n)$。总人数上限约 $2 \times 10^7$，int足够。边界：
minutes可以等于甚至（在其他变体里）超过数组长度，此时整个数组都被覆盖，答案是全部顾客；grumpy可能全 0，此时技能毫无用处，挽回值为 0；customers[i]可以为 0，不影响逻辑。
解法：滑动窗口维护有效区间
核心思路
技能不会改变老板原本就不生气的分钟，因此先把这部分满意顾客记为
base：
base = Σ customers[i]（grumpy[i] == 0）。对每个位置再定义可挽回人数
gain[i]：老板生气时取customers[i]，否则取 0。使用技能后的额外收益，就是某个长度恰为minutes的连续区间内gain的总和。问题因此变成：求gain的定长最大窗口和。相邻窗口只相差两个位置。窗口从
[left, right - 1]右移到[left + 1, right]时，加上gain[right]，减去gain[left]，无需重新遍历整个窗口。窗口不变量：初始化后，
window等于[0, minutes - 1]内的可挽回人数；每次右移完成后，window恰好等于[right - minutes + 1, right]内的可挽回人数，best是截至当前枚举过的所有合法窗口中的最大值。正确性：任意顾客只会落入两类：
grumpy[i] == 0时一定满意，被base统计；grumpy[i] == 1时只有被技能窗口覆盖才满意，被对应窗口的gain统计，两部分互不重叠。滑动窗口又不重不漏地枚举了每个长度为minutes的区间，所以best是技能能带来的最大额外收益，base + best即为最优答案。
解题步骤
- 遍历数组，累加所有
grumpy[i] == 0的customers[i]，得到固定收益base。- 统计前
minutes个位置中grumpy[i] == 1的顾客数，得到首个合法窗口的window，并令best = window。- 从
right = minutes开始向右移动窗口：加入right位置的可挽回人数，再移除right - minutes位置的可挽回人数，然后更新best。- 返回
base + best。样例
customers = [1,0,1,2,1,1,7,5]、grumpy = [0,1,0,1,0,1,0,1]、minutes = 3中，base = 1 + 1 + 1 + 7 = 10。各窗口的额外收益依次为0、2、2、3、1、6，最大值为 6，因此答案是 16。边界也由同一逻辑覆盖：
minutes == customers.length时只枚举整个数组，答案是全部顾客；grumpy全为 0 时每个窗口收益都是 0；所有生气分钟人数都为 0 时同样返回base。
代码实现
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int base = 0;
for (int i = 0; i < customers.length; i++) {
if (grumpy[i] == 0) {
base += customers[i];
}
}
int window = 0;
for (int i = 0; i < minutes; i++) {
if (grumpy[i] == 1) {
window += customers[i];
}
}
int best = window;
for (int right = minutes; right < customers.length; right++) {
if (grumpy[right] == 1) {
window += customers[right];
}
int left = right - minutes;
if (grumpy[left] == 1) {
window -= customers[left];
}
best = Math.max(best, window);
}
return base + best;
}
}
func maxSatisfied(customers []int, grumpy []int, minutes int) int {
base := 0
for i, customer := range customers {
if grumpy[i] == 0 {
base += customer
}
}
window := 0
for i := 0; i < minutes; i++ {
if grumpy[i] == 1 {
window += customers[i]
}
}
best := window
for right := minutes; right < len(customers); right++ {
if grumpy[right] == 1 {
window += customers[right]
}
left := right - minutes
if grumpy[left] == 1 {
window -= customers[left]
}
if window > best {
best = window
}
}
return base + best
}
复杂度分析
- 时间复杂度：$O(n)$。求
base、初始化首窗和移动窗口都是线性过程，每个位置只参与常数次计算。- 空间复杂度：$O(1)$。只维护固定收益、当前窗口和最大窗口三个标量，没有创建额外数组。
关键点总结
- 先拆出不受决策影响的
base，再只优化技能带来的gain，可以避免重复计数。- 「连续、长度固定、选一次」直接对应定长滑动窗口。
- 窗口右移时，加的是
right，减的是right - minutes；两个条件必须分别查看对应位置的grumpy。- 正确性来自两层完备性：
base与窗口收益覆盖全部满意顾客，滑窗枚举全部合法技能区间。
易错点总结
- 把窗口内全部顾客都算作额外收益：
customers = [100,1]、grumpy = [0,1]、minutes = 1时会把本已满意的 100 人重复计算，错误得到 200；正确答案是base 100 + best 1 = 101。- 移出时仍判断
grumpy[right]：窗口离开的元素由left = right - minutes决定，判断错下标会让旧贡献残留在window中，破坏窗口不变量。- 滑动时减去
right - minutes + 1：该位置仍在新窗口里，真正离开的是right - minutes，这是最常见的差一错误。- 只计算首窗或漏掉首窗：移动循环只覆盖第二个及之后的窗口，因此必须先用首窗初始化
best。- 重新遍历每个窗口：结果虽正确，但会退化为 $O(n \cdot minutes)$；相邻窗口的重叠部分应通过一次加法和一次减法复用。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 643. 子数组最大平均数 I | 简单 | 最纯粹的定长窗口求和，没有 base 剥离与条件累加，适合先把增量维护写熟 |
| 1456. 定长子串中元音的最大数目 | 中等 | 窗口内维护的是「满足条件的元素个数」而非人数和，判据从数值变成集合归属 |
| 1151. 最少交换次数来组合所有的 1 | 中等 | 窗口长度由数组中 1 的总数决定，求的是窗口内 0 的最小值而非最大值 |
| 1423. 可获得的最大点数 | 中等 | 取的是首尾两段，需要先转化成「求中间长度固定的最小子数组和」才能套定长窗口 |
| 209. 长度最小的子数组 | 中等 | 变长窗口的代表：窗口可能不合法，必须先收缩左端点再更新答案 |
| 1004. 最大连续1的个数 III | 中等 | 同样是「有限次改写」的加成模型，但改写次数是 k 次且位置不必连续，退化成变长窗口 |
| 438. 找到字符串中所有字母异位词 | 中等 | 定长窗口内维护的是字符计数表，增量更新的对象从标量升级成数组 |