LeetCode 1052. 愛生氣的書店老闆（定長滑動視窗圖解）

1052. 愛生氣的書店老闆

題目描述

有一個書店老闆，他的書店開了 n 分鐘。每分鐘都有一些顧客進入這家商店。給定一個長度為 n 的整數陣列 customers，其中 customers[i] 是在第 i 分鐘開始時進入商店的顧客數量，所有這些顧客在第 i 分鐘結束後離開。

在某些分鐘內，書店老闆會生氣。如果書店老闆在第 i 分鐘生氣，那麼 grumpy[i] = 1，否則 grumpy[i] = 0。

當書店老闆生氣時，那一分鐘的顧客就會不滿意；若老闆不生氣，則顧客是滿意的。

書店老闆知道一個祕密技巧，能抑制自己的情緒，可以讓自己連續 minutes 分鐘不生氣，但只能使用一次。

請回傳這一天營業下來，最多有多少客戶能夠感到滿意。

輸入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
輸出：16
解釋：書店老闆在最後 3 分鐘保持冷靜。
感到滿意的最大客戶數量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

輸入：customers = [1], grumpy = [0], minutes = 1
輸出：1

限制：

• n == customers.length == grumpy.length
• 1 <= minutes <= n <= 2 * 10^4
• 0 <= customers[i] <= 1000
• grumpy[i] == 0 or 1

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解為自行補充。

思路

本題可以拆成兩個問題：

1. 老闆不生氣時的顧客數量總和 s0。這些顧客本來就滿意。
2. 長度為 minutes 的連續子陣列中，「老闆生氣時的顧客數量」總和 s1 的最大值 maxS1。這些顧客靠祕密技巧被救回來。

最終答案為 s0 + maxS1。

第二個問題可以用定長滑動視窗解決。以 customers=[3,1,4,1,5,9]、grumpy 全為 1、minutes=3 為例：

1. 第一個長為 3 的視窗和：3+1+4 = 8。
2. 往右滑一格：加上 customers[3]=1，減去 customers[0]=3，得 8+1-3 = 6。
3. 再滑一格：加 customers[4]=5，減 customers[1]=1，得 6+5-1 = 10。
4. 再滑一格：加 customers[5]=9，減 customers[2]=4，得 10+9-4 = 15。

最大的視窗和為 15。

為什麼要分開計算不生氣與生氣的顧客？ 因為不生氣的顧客可能落在視窗外面，必須獨立計算；視窗只需要關心「生氣的分鐘」能多救回幾人。

圖解（可互動）

使用範例 1：customers = [1,0,1,2,1,1,7,5]、grumpy = [0,1,0,1,0,1,0,1]、minutes = 3。按「下一步」觀察視窗右移時 s1（視窗內生氣的顧客數）與 maxS1 的變化。

上一步 下一步 重置

customers = [1,0,1,2,1,1,7,5]，grumpy = [0,1,0,1,0,1,0,1]，minutes = 3

老闆生氣（grumpy = 1） 老闆不生氣（grumpy = 0） 視窗內 入 = 新進入 出 = 剛離開

不生氣總和 s00

視窗內生氣顧客 s10

目前最大值 maxS10

解法（灵茶山艾府）

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int[] s = new int[2];
        int maxS1 = 0;
        for (int i = 0; i < customers.length; i++) {
            s[grumpy[i]] += customers[i];
            int left = i - minutes + 1; // 窗口左端點
            if (left < 0) { // 窗口長度不足 minutes
                continue;
            }
            maxS1 = Math.max(maxS1, s[1]);
            // 窗口最左邊元素離開窗口
            s[1] -= grumpy[left] > 0 ? customers[left] : 0;
        }
        return s[0] + maxS1;
    }
}

這裡 s[0] 累計整天不生氣時的顧客（不會被扣掉），s[1] 則是視窗內生氣時的顧客，視窗左端離開時才扣除。

複雜度分析

• 時間複雜度：O(n)，其中 n 為 customers 的長度。
• 空間複雜度：O(1)。