1052. Grumpy Bookstore Owner

Leetcode link

解题思路

本题题目说的有点模糊，我简单用自己的语言描述一下题意

题目给了我们三个参数：

• customers：Array，代表在第 n 分钟进来的客人数量，所有的客人都会一直呆到关门
• grummpy：Array，取值为 0 或 1，0 代表店主脾气很好，此时客人会很满意；1 代表此时店主脾气暴躁，此时进来的客人会很不满（但是不会离开，也不会影响之前或之后进来的客人）
• minutes：Number，店主得到高人指点，习得了抑制脾气的方法（参考班纳压抑绿巨人的情况）但是这个方法只能持续一段固定的连续时间，这段时间的长度就是 minutes

题目要求我们求店主最多能让多少顾客满意

这一题最主要的思路就是把固定的部分与变化的部分分开计算：

• 固定的部分：指的是店主脾气好的时候进来的客人，这一组客人始终都是满意的
• 变化的部分：值得是店主脾气不好的时候进来的客人，这一部分客人的满意度取决于店主有没有在这个时间段使用技巧

固定的部分很好计算，只要把 grumpy 是 0 的时间段进来的客人数量全部加起来就好

变化的部分就需要用到滑动窗口来求解了，我们把 minutes 的长度当成窗口，通过窗口的滑动来计算每一个窗口能让本来不满意的顾客（grumpy 为 0 的时候进来的顾客）满意的数量，最后求所有可能的最大值就好

为了方便理解，我写了两个版本，第一个版本用到了两次循环，更加方便理解；第二个版本直接把两个循环合在一起了，复杂度降低胃了 O(n)

Javascript——方便理解版

/**
 * @param {number[]} customers
 * @param {number[]} grumpy
 * @param {number} minutes
 * @return {number}
 */
var maxSatisfied = function (customers, grumpy, minutes) {
    // calculate the initial satisfication for all customers
    let initSatisfication = 0;
    for (let i = 0; i < customers.length; i++) {
        if (grumpy[i] === 0) {
            initSatisfication += customers[i];
        }
    }

    // use slide window to calculate the max extra satisfication before using technique
    let index = 0;
    let maxExtra = 0;
    while (index + minutes <= customers.length) {
        let extra = 0;
        for (let i = index; i < index + minutes; i++) {
            if (grumpy[i] === 1) {
                extra += customers[i];
            }
        }
        maxExtra = Math.max(extra, maxExtra);
        index++;
    }

    return initSatisfication + maxExtra;
};

Javascript——时间复杂度 O(n) 版

/**
 * @param {number[]} customers
 * @param {number[]} grumpy
 * @param {number} minutes
 * @return {number}
 */
var maxSatisfied = function (customers, grumpy, minutes) {
    // use for sliding window
    let left = 0, right = 0;
    // satisfication without technique
    let initSatisfication = 0;
    // satisfication using technique
    let extra = 0, maxExtra = 0;

    while (right < grumpy.length) {
        if (grumpy[right] === 0) {
            initSatisfication += customers[right];
        }

        if (right < minutes) {
            if(grumpy[right] === 1) extra += customers[right];
        } else {
            // reset the window(remove the left one, add the right one)
            if (grumpy[left] === 1) extra -= customers[left];
            if (grumpy[right] === 1) extra += customers[right];
            left++;
        }

        if (right >= minutes - 1) {
            maxExtra = Math.max(extra, maxExtra);
        }
        right++;
    }
    return initSatisfication + maxExtra;
}