🔗 🟡 1052. Grumpy Bookstore Owner 1418

tags: `Week Contest 138` `前綴和(Prefix Sum)` `滑動窗口(Sliding Window)`

題意

有一個書店老闆經營著一家營業 $n$ 分鐘的書店。每分鐘都會有一些顧客進入店裡。給定一個整數陣列 $\text{customers}$ ，長度為 $n$ ，其中 $\text{customers}[i]$ 是第 $i$ 分鐘開始時進入店內的顧客數量，這些顧客在那分鐘結束後離開。

但在某些時候，書店老闆心情不太好。給定一個二進位陣列 $\text{grumpy}$ ，其中 $\text{grumpy}[i]$ 為 $1$ 表示書店老闆在第 $i$ 分鐘心情不好，為 $0$ 表示心情好。

當書店老闆心情不好時，該分鐘的顧客就不滿意，否則就是滿意的。

書店老闆知道一個讓自己連續 $minutes$ 分鐘保持心情好的秘訣，但每天只能使用一次。

回傳最大的滿意顧客數量。

思路

方法一：前綴和(Prefix Sum)

對於每一分鐘，若該分鐘老闆心情本來就是好的，則不用考慮是否需要使用秘訣。因此可以先計算在老闆心情好時的顧客數量 $tot$ 。如此便只需要考慮老闆心情不好的時刻即可。

由於使用秘訣後可以使老闆連續 $minutes$ 分鐘保持心情好，因此可以枚舉每個大小為 $minutes$ 的區間，計算區間內在老闆心情不好時的顧客數量總和。但每次區間求和需要 $\mathcal{O}(n)$ 時間，因此需要使用前綴和(Prefix Sum) 來解決問題，將區間求和的時間複雜度降為 $\mathcal{O}(1)$ 。

令 $s[i]$ 表示前 $i$ 分鐘老闆不開心時的顧客數量總和，則可以事先計算出每個位置的前綴和，即 $s[i+1] = s[i] + customers[i] \times grumpy[i]$ ，則區間 $[i, j]$ 的和即為 $s[j+1] - s[i]$ （下標從 $0$ 開始）。

令 $ans$ 為最大的區間和，則可以枚舉每個區間 $[i, i+minutes-1]$ 並計算區間和，最後返回 $tot + ans$ 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n)$ 。

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        tot = sum(customers[i] for i in range(n) if not grumpy[i])
        s = [0] * (n+1)
        for i in range(n):
            s[i+1] = s[i] + customers[i] * grumpy[i]
        ans = 0
        for i in range(n - minutes + 1):
            ans = max(ans, s[i+minutes] - s[i])
        return tot + ans

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int n = customers.size(), tot = 0, ans = 0;
        vector<int> s(n + 1);  // prefix sum
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + customers[i] * grumpy[i];
            tot += customers[i] * (1 ^ grumpy[i]);
        }
        for (int i = 0; i <= (n - minutes); i++)
            ans = max(ans, s[i + minutes] - s[i]);
        return tot + ans;
    }
};

方法二：滑動窗口(Sliding Window)

由於使用秘訣後可以使老闆連續 $minutes$ 分鐘保持心情好，因此可以維護一個大小為 $minutes$ 的窗口，使用滑動窗口(Sliding Window) 來解決問題。

令 $cur$ 紀錄當前窗口內，在老闆不開心的情況下的顧客數量、 $ans$ 表示最大的窗口值。則可以將 $cur$ 初始化為前 $minutes$ 分鐘老闆不開心時的顧客數量總和。之後從 $minutes$ 分鐘開始遍歷，每次更新 $cur$ 為 $cur + customers[i] \times grumpy[i] - customers[i - minutes] \times grumpy[i - minutes]$ ，即加上當前分鐘的顧客數量，減去窗口左側的顧客數量。最後返回 $tot + ans$ 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        tot = sum(customers[i] for i in range(n) if not grumpy[i])
        ans = cur = sum(customers[i] * grumpy[i] for i in range(minutes))
        for i in range(minutes, n):
            cur += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes]
            ans = max(ans, cur)
        return tot + ans

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int n = customers.size(), tot = 0, cur = 0;
        for (int i = 0; i < n; i++) tot += customers[i] * (1 ^ grumpy[i]);
        for (int i = 0; i < minutes; i++) cur += customers[i] * grumpy[i];
        int ans = cur;
        for (int i = minutes; i < n; i++) {
            cur += customers[i] * grumpy[i] -
                   customers[i - minutes] * grumpy[i - minutes];
            ans = max(ans, cur);
        }
        return tot + ans;
    }
};