leetcode中如何解決愛生氣書店老板問題

這篇文章給大家分享的是有關(guān)leetcode中如何解決愛生氣書店老板問題的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

一、題目內(nèi)容

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

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

書店老板知道一個秘密技巧，能抑制自己的情緒，可以讓自己連續(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

二、解題思路

滑動窗口，沒啥說的，先累加能獲得的所有滿意度，然后再計算滑動窗口中能獲得的滿意度，每次需要記錄最大值，最后返回二者之和即可。

三、代碼

class Solution:
    def maxSatisfied(self, customers: list, grumpy: list, X: int) -> int:
        origin = 0
        for i in range(len(customers)):
            if grumpy[i] == 0:
                origin += customers[i]
        # print(origin)
        windows = 0
        for i in range(X):
            if grumpy[i] == 1:
                windows += customers[i]
        # print(windows)
        left = 0
        right = X - 1
        dynamic = windows
        while right < len(customers) - 1:
            if grumpy[left] == 1:
                dynamic -= customers[left]

            if grumpy[right + 1] == 1:
                dynamic += customers[right + 1]
            left += 1
            right += 1
            windows = max(windows, dynamic)
        return origin + windows


if __name__ == '__main__':
    s = Solution()
    customers = [1, 0, 1, 2, 1, 1, 7, 5]
    grumpy = [0, 1, 0, 1, 0, 1, 0, 1]
    X = 3
    ans = s.maxSatisfied(customers, grumpy, X)
    print(ans)

感謝各位的閱讀！關(guān)于“l(fā)eetcode中如何解決愛生氣書店老板問題”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！