LeetCode-Go 题解：1052. Grumpy Bookstore Owner（滑动窗口经典应用，Go 实现详解）

LeetCode-Go 题解：1052. Grumpy Bookstore Owner（滑动窗口经典应用，Go 实现详解）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇以 LeetCode-Go 仓库中 1052. Grumpy-Bookstore-Owner 题解目录 的 README.md 为主体，结合仓库内的 Go 源码与测试用例，完整讲解「Grumpy Bookstore Owner（爱生气的书店老板）」这道滑动窗口经典题。读完本文，你将掌握该题的暴力枚举思路与 O(n) 滑动窗口优化写法，并理解如何把"在 0/1 数组中选一段连续区间"的问题统一抽象为可复用的滑动窗口范式。

题目描述

书店老板的店将试营业customers.length分钟。每一分钟都会有若干顾客（customers[i]）进入书店，并在该分钟结束时离开。

在部分分钟里，书店老板是生气的：如果第i分钟老板生气，则grumpy[i] = 1，否则grumpy[i] = 0。老板生气时，该分钟的顾客会感到不满意；老板不生气时，该分钟的顾客感到满意。

老板掌握一个秘密技巧，可以让自己连续X分钟不生气，但这个技巧只能使用一次。

请返回全天营业下来，最多能有多少顾客感到满意。

示例与数据范围

示例：

输入: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 输出: 16 解释: 老板在最后 3 分钟保持不生气。 最多可满意的顾客数 = 1 + 1 + 1 + 1 + 7 + 5 = 16。

约束：

问题抽象：从"书店场景"到"价值数组 + 0/1 数组"

把题目的业务场景抽象掉，问题可以等价描述为（这也是 README.md 给出的核心洞察）：

• 给定一个价值数组customers；
• 给定一个装着 0 和 1 的数组grumpy（两者下标一一对应）；
• 当价值数组某个下标对应的grumpy值为0时，该价值可以累加；为1时不能累加；
• 现在允许把grumpy数组中连续X个数全部变成0，问最终累计价值最大是多少。

换句话说，老板的"秘密技巧"本质上是：在长度为n的 0/1 序列中，选择一段长度为X的连续子区间，把区间内的1全部翻转成0，从而把这些分钟对应的顾客价值"抢救"回来。目标就是让抢救回来的价值最大。

解法一：暴力滑动窗口（思路铺垫）

最直观的思路是：用窗口右边界不断向右扩展，当窗口宽度等于X时，计算此刻整个数组的总价值；窗口滑过整个数组后，输出维护到的最大值。

仓库中的暴力版实现为 1052. Grumpy Bookstore Owner.go 中的maxSatisfied1函数：

// 解法二 滑动窗口暴力版 func maxSatisfied1(customers []int, grumpy []int, X int) int { left, right, res := 0, -1, 0 for left < len(customers) { if right+1 < len(customers) && right-left < X-1 { right++ } else { if right-left+1 == X { res = max(res, sumSatisfied(customers, grumpy, left, right)) } left++ } } return res }

辅助函数sumSatisfied负责计算"将[start, end]区间内的 1 全部视为 0"之后的总价值：

func sumSatisfied(customers []int, grumpy []int, start, end int) int { sum := 0 for i := 0; i < len(customers); i++ { if i < start || i > end { if grumpy[i] == 0 { sum += customers[i] } } else { sum += customers[i] } } return sum }

该解法的时间复杂度为O(n × X)：窗口每滑动一次就要重新遍历整个数组求和。当n达到 20000 时，这种方法耗时较长，存在明显的优化空间。

解法二：滑动窗口优化版（O(n)）

核心思想：只关心窗口内为 1 的部分

仔细分析可以发现，每次计算总价值时，其实真正需要回答的问题是：

宽度为X的窗口内，grumpy == 1对应的顾客价值累加和最大是多少？

原因在于：

• grumpy == 0的分钟本来就满意，无论技巧用在哪里，这些价值都必然被计入，它们不受窗口位置影响；
• 只有grumpy == 1的分钟会因为"被技巧覆盖"而从"不满意"变成"满意"，因此技巧的收益完全取决于窗口内1对应的价值总和；
• 把窗口内1对应的价值累加和最大化，等价于让技巧带来的收益最大化。

因此引入两个独立变量（这也是 README.md 解题思路的核心结论）：

• customer0：累加所有grumpy[i] == 0分钟对应的顾客价值——这一部分是固定收益，不管怎么改变都不会丢；
• customer1：窗口内grumpy[i] == 1分钟对应的顾客价值累加和——窗口滑动时动态维护；
• maxCustomer1：滑动过程中customer1的最大值——即技巧能带来的最大增量收益。

最终答案就是customer0 + maxCustomer1。

源码逐行拆解

优化版实现同样位于 1052. Grumpy Bookstore Owner.go，完整代码如下：

// 解法一 滑动窗口优化版 func maxSatisfied(customers []int, grumpy []int, X int) int { customer0, customer1, maxCustomer1, left, right := 0, 0, 0, 0, 0 for ; right < len(customers); right++ { if grumpy[right] == 0 { customer0 += customers[right] } else { customer1 += customers[right] for right-left+1 > X { if grumpy[left] == 1 { customer1 -= customers[left] } left++ } if customer1 > maxCustomer1 { maxCustomer1 = customer1 } } } return maxCustomer1 + customer0 }

逐步说明：

1. 固定收益累计：right指针每扩展一位，若grumpy[right] == 0，直接把customers[right]累加进customer0。这部分价值与窗口位置无关，是"保底收益"。
2. 窗口内动态收益维护：若grumpy[right] == 1，先把customers[right]加进customer1；随后用内层for循环收缩左边界，保证窗口宽度right-left+1不超过X。左边界滑出窗口时，如果grumpy[left] == 1，就从customer1中减掉customers[left]。
3. 最大值跟踪：每次维护完合法窗口后，用maxCustomer1记录customer1出现过的最大值。
4. 返回：maxCustomer1 + customer0即为全天最多能满意的顾客数。

关于内层循环的执行次数：由于left在整个算法中只增不减，内层for的总体代价是 O(n)，因此整体时间复杂度为O(n)，空间复杂度为O(1)（仅用常数个整型变量）。相比暴力版，这是从 O(n×X) 到 O(n) 的质的提升。

用示例完整推演一遍

以题目示例customers = [1,0,1,2,1,1,7,5]、grumpy = [0,1,0,1,0,1,0,1]、X = 3为例：

最终customer0 = 10，maxCustomer1 = 8，答案10 + 8 = 16，与题目输出一致。窗口落在最后 3 分钟（下标 5、6、7 中生气的是 5 和 7），恰好对应"老板在最后 3 分钟不生气"的最优方案。

测试用例与验证方式

仓库为该题提供了单元测试文件 1052. Grumpy Bookstore Owner_test.go，覆盖了 3 组用例：

其中第一组用例检验"窗口覆盖前两个生气分钟"的场景：customer0 = 10（第 2 分钟），窗口[0,1]内1的价值为4+10=14，答案10 + 14 = 24；第二组用例覆盖最小规模（单分钟）的边界情况；第三组即题目官方示例。

在仓库根目录下，可以通过 gotest.sh 中的命令一键运行全部题解测试并生成覆盖率报告：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

该命令会对leetcode/下所有题解包执行测试并产出 coverage.txt。仓库中 coverage.txt 已包含本文件的覆盖率记录（1052. Grumpy Bookstore Owner.go各代码块均被测试执行到），符合本仓库"100% test coverage"的题解质量约定。也可单独运行本目录测试：

go test -v ./leetcode/1052.Grumpy-Bookstore-Owner/

本题在滑动窗口题型中的定位

仓库的 ctl/template/Sliding_Window.md 中，将第 1052 题明确列入"双指针滑动窗口经典写法"的推荐题单（同题单还包括第 3、76、209、424、438、567、713、763、845、881、904、978、992、1004、1040 题），并给出了通用的滑动窗口框架：

left, right := 0, -1 for left < len(s) { if right+1 < len(s) && freq[s[right+1]-'a'] == 0 { freq[s[right+1]-'a']++ right++ } else { freq[s[left]-'a']-- left++ } result = max(result, right-left+1) }

本题的优化版正是该框架的一个变体：右指针持续右移（扩展窗口），一旦窗口宽度超过X就移动左指针（收缩窗口），并在每个合法窗口处更新最优解。区别在于本题"窗口内统计的量"是grumpy == 1时的顾客价值，而非字符频率——这体现了滑动窗口思想在不同场景下的复用方式。仓库中同属滑动窗口分类的题目图片 topic/Sliding_Window.png 展示了该分类下各题的分布情况，可作为进一步刷题的参考索引。

总结

• 本题是典型的"定长窗口"滑动窗口问题，核心技巧是把答案拆成两部分：customer0（固定收益）与窗口内1价值的最大累加和maxCustomer1（技巧收益）；
• 暴力解法 O(n×X) 便于理解，但会在每次窗口滑动时重复遍历数组；
• 优化解法仅用left、right两个指针维护窗口，边扩展边收缩，整体 O(n) 时间、O(1) 空间，并已通过仓库内单元测试验证（见 1052. Grumpy Bookstore Owner_test.go）；
• 该题在 LeetCode-Go 仓库中被归类到滑动窗口经典题单（见 ctl/template/Sliding_Window.md），是掌握"右指针扩展 + 左指针收缩"双指针范式的最佳入门题之一。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go