Skip to content

Latest commit

 

History

History
201 lines (153 loc) · 6.21 KB

29.grumpy-bookstore-owner.md

File metadata and controls

201 lines (153 loc) · 6.21 KB
Raw

1052. 爱生气的书店老板

https://leetcode-cn.com/problems/grumpy-bookstore-owner/

题目描述

今天，书店老板有一家店打算试营业 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))$，非良解。

关于长度固定的滑动窗口，有一点我们要熟悉的是，窗口每次滑动时，变化的只有头尾两个元素，所以我们只针对这两个元素进行处理就行。

具体怎么写代码注释已经很详细啦，下方有三个版本的代码 ╮（╯＿╰）╭

  • 啰嗦版本
  • 简洁版本
  • 一次遍历版本

思路本质上是一样的，复杂度也是一样的，只是写法不同。

复杂度分析

  • 时间复杂度：$O(N)$，N 为数组长度。
  • 空间复杂度：$O(1)$。

代码(啰嗦版本)

JavaScript Code

/**
 * @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

/**
 * @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 && grumpy[i]) total += customers[i];
        // 滑动窗口右移中，(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

/**
 * @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 && grumpy[i]) total += customers[i];
        // 滑动窗口右移中，(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;
};