滑动窗口，简单详细易懂 爱生气的书店老板 力扣每日一题

思路

这里只要能判断出用完魔法后的minutes内滑动窗口的最大的提升是多少，然后遍历一遍，把老板不生气的顾客总数加上最大的提升就好 我们可以用滑动窗口的思想，每次保证窗口大小是minutes大小，统计一下每次这个窗口内的老板生气的customers的总数，用一个变量来记录所有这些大小的窗口的最大的这个customers，就是可以提升的最大数。 如果mintues为1的话就不需要用滑动窗口，直接遍历一遍找到grumpy为1且customers最大的即为最大的提升。

复杂度

• 时间复杂度: O(n)O(n) O(n)

• 空间复杂度: O(n)O(n) O(n)

Code
 

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        left, ans, max_promate = 0, 0, 0
        if minutes!=1:
            for right in range(minutes - 1, len(customers)):
                if right - left + 1 > minutes:
                    left += 1
                sum_angry = 0
                for i in range(left, right + 1):
                    if grumpy[i] == 1:
                        sum_angry += customers[i]
                max_promate = max(max_promate, sum_angry)


        else:
            for right in range(len(customers)):
                if grumpy[right]==1:
                    max_promate=max(customers[right],max_promate)

        for i, x in enumerate(customers):
            if grumpy[i] == 0:
                ans += x
        return ans + max_promate

作者：学不好计算机不改名
链接：https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/2988431/hua-dong-chuang-kou-jian-dan-xiang-xi-yi-p0t2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

原文地址：https://blog.csdn.net/qq_17405059/article/details/143772868

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！