難度：★★★☆☆
類型：數(shù)組
方法：滑動窗口

題目

力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄

今天，書店老板有一家店打算試營業(yè) customers.length 分鐘。每分鐘都有一些顧客（customers[i]）會進入書店，所有這些顧客都會在那一分鐘結(jié)束后離開。

在某些時候，書店老板會生氣。 如果書店老板在第 i 分鐘生氣，那么 grumpy[i] = 1，否則 grumpy[i] = 0。 當書店老板生氣時，那一分鐘的顧客就會不滿意，不生氣則他們是滿意的。

書店老板知道一個秘密技巧，能抑制自己的情緒，可以讓自己連續(xù) X 分鐘不生氣，但卻只能使用一次。

請你返回這一天營業(yè)下來，最多有多少客戶能夠感到滿意的數(shù)量。

示例：

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

提示：

1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1

解答

一看題目，是個一維數(shù)組的題目，出現(xiàn)【連續(xù)】二字，很容易想到使用滑動窗口來解決。

如果題目是這樣，讓求一個數(shù)組指定長度的連續(xù)子數(shù)組的最大和，我們很容易寫出算法。大概會是這樣，維護一個起點在i位置，長度為X的滑動窗口：

from typing import List
class Solution:
    def maxSatisfied(self, customers: List[int], X: int) -> int:
        s = sum(customers[:X])
        ans = s
        for i in range(len(customers)-X):
            s += customers[X+i]
            s -= customers[i]
            ans = max(ans, s)
        return ans

我們通過使用中間變量s來避免重復(fù)的加法運算。循環(huán)中每次執(zhí)行的操作實際上是X+i位置處元素的加入以及i位置處元素的去除。

這道題增加了一個限制條件，也就是通過數(shù)組grumpy控制customers數(shù)組中相應(yīng)數(shù)字的選擇與否。因此在中間變量s的更新時，需要根據(jù)grumpy中相應(yīng)的狀態(tài)，來控制s更新的具體數(shù)值。

from typing import List
class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        s = sum(c for i, (c, g) in enumerate(zip(customers, grumpy)) if g == 0 or i < X)
        ans = s
        for i in range(len(customers)-X):
            s += customers[X+i] if grumpy[X+i] else 0
            s -= customers[i] if grumpy[i] else 0
            ans = max(ans, s)
        return ans

如有疑問或建議，歡迎評論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請移步力扣中等題解析