> For the complete documentation index, see [llms.txt](https://suki.gitbook.io/91-days-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/29.grumpy-bookstore-owner.md). # 1052. 爱生气的书店老板 * [1052. 爱生气的书店老板](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/pages/-MNWDonunVidzKxsEZat#1052-爱生气的书店老板) * [题目描述](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/pages/-MNWDonunVidzKxsEZat#题目描述) * [方法 1：滑动窗口](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/pages/-MNWDonunVidzKxsEZat#方法-1滑动窗口) * [思路](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/pages/-MNWDonunVidzKxsEZat#思路) * [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/pages/-MNWDonunVidzKxsEZat#复杂度分析) * [代码(啰嗦版本)](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/pages/-MNWDonunVidzKxsEZat#代码啰嗦版本) * [代码(简洁版本)](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/pages/-MNWDonunVidzKxsEZat#代码简洁版本) * [代码(一次遍历的版本)](https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/pages/-MNWDonunVidzKxsEZat#代码一次遍历的版本) ## 题目描述 ``` 今天，书店老板有一家店打算试营业 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. 提示： 1 <= X <= customers.length == grumpy.length <= 20000 0 <= customers[i] <= 1000 0 <= grumpy[i] <= 1 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/grumpy-bookstore-owner 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ``` ## 方法 1：滑动窗口 ### 思路 根据题目信息，书店老板可以 `让自己连续 X 分钟不生气`，那我们可以： * 先让他在 `[0, X]` 这段时间不生气，计算此时满意的顾客数。 * 然后让他在 `[1, X+1]` 这段时间不生气，计算满意的顾客。 * ...... * 让他在 `[N-X, N]` 这段时间不生气，计算满意的顾客。 其实就是用一个长度为 X 的滑动窗口来遍历数组，并在这个过程中找出满意顾客数的最大值。 关键问题是，如何计算满意顾客的数量？naive 的想法当然是滑动窗口每次滑动时，都遍历一次数组进行计算，但这种做法时间复杂度是 $O(N\*(N-X))$，非良解。 关于长度固定的滑动窗口，有一点我们要熟悉的是，窗口每次滑动时，变化的只有头尾两个元素，所以我们只针对这两个元素进行处理就行。 ![](https://cdn.jsdelivr.net/gh/suukii/91-days-algorithm/assets/1052_0.png) 具体怎么写代码注释已经很详细啦，下方有三个版本的代码 ╮（╯＿╰）╭ * 啰嗦版本 * 简洁版本 * 一次遍历版本 思路本质上是一样的，复杂度也是一样的，只是写法不同。 ### 复杂度分析 * 时间复杂度：$O(N)$，N 为数组长度。 * 空间复杂度：$O(1)$。 ### 代码(啰嗦版本) JavaScript Code ```javascript /** * @param {number[]} customers * @param {number[]} grumpy * @param {number} X * @return {number} */ var maxSatisfied = function (customers, grumpy, X) { let total = 0; // 首先计算老板不生气时的所有满意顾客 // 这些顾客无论在不在情绪控制区都没有影响的 for (let i = 0; i < customers.length; i++) { if (!grumpy[i]) total += customers[i]; } // 然后滑出一个长度为 X 的窗口 // 这段是情绪控制区，所以原来不满意的顾客也变成满意的了 let l = 0, r = 0; while (r < X) { if (grumpy[r]) total += customers[r]; r++; } let max = total; // 窗口右移 // r 指针回到滑动窗口的右边界 r--; while (r < customers.length - 1) { // l 即将离开情绪控制区，如果原本是不满意的顾客，就恢复不满意啦 if (grumpy[l]) total -= customers[l]; l++; r++; // r 进入了情绪控制区，不满意顾客变成满意的了 if (grumpy[r]) total += customers[r]; if (total > max) max = total; } return max; }; ``` ### 代码(简洁版本) JavaScript Code ```javascript /** * @param {number[]} customers * @param {number[]} grumpy * @param {number} X * @return {number} */ var maxSatisfied = function (customers, grumpy, X) { let total = 0; // 先计算老板不生气时的所有满意顾客 for (let i = 0; i < customers.length; i++) { if (!grumpy[i]) total += customers[i]; } let max = total; for (let i = 0; i < customers.length; i++) { // 第一个滑动窗口，如果其中有不满意的顾客，将他们改成满意的 if (i < X) total += grumpy[i] ? customers[i] : 0; // 滑动窗口右移中，(i - X, i] 这段就是滑动窗口 else { // 左边界离开情绪控制区，如果原本是不满意的顾客，就恢复不满意啦 if (grumpy[i - X]) total -= customers[i - X]; // 右边界进入情绪控制区，不满意顾客变成满意的了 if (grumpy[i]) total += customers[i]; } if (total > max) max = total; } return max; }; ``` ### 代码(一次遍历的版本) JavaScript Code ```javascript /** * @param {number[]} customers * @param {number[]} grumpy * @param {number} X * @return {number} */ var maxSatisfied = function (customers, grumpy, X) { // 老板不生气时的所有满意顾客 let got = 0, // 老板控制情绪时滑动窗口中增加的满意顾客，也就是滑动窗口中原本不满意的顾客 total = 0, // 在滑动窗口移动过程中 total 的最大值 max = 0; for (let i = 0; i < customers.length; i++) { if (!grumpy[i]) got += customers[i]; // 第一个滑动窗口 if (i < X) total += grumpy[i] ? customers[i] : 0; // 滑动窗口右移中，(i - X, i] 这段就是滑动窗口 else { if (grumpy[i - X]) total -= customers[i - X]; if (grumpy[i]) total += customers[i]; } if (total > max) max = total; } // 原本的满意顾客 + 情绪控制区最多能收揽的不满意顾客 return got + max; }; ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://suki.gitbook.io/91-days-algorithm/basic/two-pointers/29.grumpy-bookstore-owner.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.