1052. 爱生气的书店老板

滑动窗口

方法一滑动窗口

解题思路

当书店老板不生气的时候，顾客满意度是固定的。所以生气的时候可以改变的满意度影响着最后的结果，所以这个题就转变成了求最大的可以改变的满意度。

首先遍历一边customers计算出不受影响的满意顾客数的合。并且把这些customer置为0。然后使用滑动窗口计算最大的增长量。最后返回不受影响的 + 最大增长量即可。

参考代码

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        total = 0
        for i in range(0,n):
            if grumpy[i] == 0:
                total += customers[i]
                # 把不影响结果的置为0
                customers[i] = 0
        increase = 0
        for i in range(0,minutes):
            increase += customers[i]
        max_increase = increase
        for i in range(minutes,n):
            increase = increase + customers[i] - customers[i - minutes]
            max_increase = max(max_increase,increase)
        return total + max_increase

复杂度分析

时间复杂度O(n) 遍历了两边数组
空间复杂度O(1)