LeetCode 1052. 爱生气的书店老板

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里
标签
数组 滑动窗口

题目描述

✅ 1052. 爱生气的书店老板

image-20260929073557388

image-20260929073557473

题意分析

customers[i] 表示某一分钟的顾客数，grumpy[i] 表示老板当时是否生气：不生气时这一分钟的顾客满意，生气时则不满意。老板可以使用一次技巧，在连续 minutes 分钟内保持冷静，求最多能让多少顾客满意。

技巧只覆盖一段连续时间，不能把名额分散到多个位置。原本就满意的顾客，无论窗口选在哪里都仍然满意；窗口只可能额外挽回原本生气分钟的顾客。

解法：滑动窗口维护有效区间

核心思路

[!blue]

将总收益拆成两部分。base 是所有 grumpy[i] = 0 时的顾客总数，与窗口选择无关；额外收益只来自窗口内那些 grumpy[i] = 1 的分钟。两部分对应不同顾客，相加不会重复。

因此窗口每个位置的有效贡献是：原本生气则为该分钟顾客数，否则为 0。不需要真的建立贡献数组，只在加入和移除窗口元素时检查对应的 grumpy 即可。

技巧时长固定，先算出最左边长度为 minutes 的窗口额外收益，作为 window 和当前最大值 best。之后每次向右滑动一格，新位置 right 进入，旧位置 right - minutes 离开，只需加入和减去这两个位置的有效贡献。

滑动覆盖了所有合法的连续时间段，每次维护的 window 都恰好是当前段能新增的满意人数。固定收益不变，选择最大的额外收益就是全局最优，最后返回 base + best。

解题步骤

  1. 扫描全部分钟，把原本不生气时的顾客计入 base。
  2. 计算前 minutes 个位置中原本生气部分的顾客数，作为第一个窗口收益，并初始化 best。
  3. 从下标 minutes 开始右移窗口：新进入位置若生气就加上其顾客数，离开位置若生气就减去其顾客数。
  4. 完成一次加减后更新 best，遍历结束返回 base + best。

代码实现

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)$，每个位置参与常数次计算。
  • 空间复杂度：$O(1)$，只维护固定收益、当前窗口和最大收益。

关键点总结

[!green]

  • 基础满意人数与技巧新增人数分开计算，窗口中原本满意的人不会再计一次。
  • 窗口长度固定，右移时只改变两个位置，能在线性时间遍历所有选择。
  • 首个完整窗口就可能最优，必须在继续滑动前记录它的贡献。

易错点总结

[!yellow]

  • 将窗口内全部顾客再加到 base，会重复统计本来已经满意的人。
  • 移除旧位置时仍检查新右端的生气标记，加入与移除对应不同分钟，条件必须分别读取。
  • 移出的下标写成 right - minutes + 1，减掉的仍在新窗口里，维护值就会错位。
  • 只从第二个窗口开始记录最大值，会漏掉最左窗口，窗口覆盖全数组时尤其明显。
  • 挑选若干顾客最多的生气分钟，会违反技巧必须作用于一个连续区间的限制。

相似题目

题目 难度 关联与区别
643. 子数组最大平均数 I 简单 先固定不生气时的基础收益，再用定长窗口求能挽回的最大额外收益。
1004. 最大连续1的个数 III 中等 原题允许在任意位置翻k个0，本题只能选择一个连续时间段，不能把窗口长度当自由修改预算。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/83286395
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！