跳至主要內容

1052. 爱生气的书店老板

ITCharge大约 2 分钟

1052. 爱生气的书店老板open in new window

  • 标签:数组、滑动窗口
  • 难度:中等

题目大意

书店老板有一家店打算试营业 len(customers) 分钟。每一分钟都有一些顾客 customers[i] 会进入书店,这些顾客会在这一分钟结束后离开。

在某些时候,书店老板会生气。如果书店老板在第 i 分钟生气,则 grumpy[i] = 1,如果第 i 分钟不生气,则 grumpy[i] = 0。当书店老板生气时,这一分钟的顾客会不满意。当书店老板不生气时,这一分钟的顾客是满意的。

假设老板知道一个秘密技巧,能保证自己连续 minutes 分钟不生气,但只能使用一次。

现在给定代表每分钟进入书店的顾客数量的数组 customes,和代表老板生气状态的数组 grumpy,以及老板保证连续不生气的分钟数 minutes

要求:计算出试营业下来,最多有多少客户能够感到满意。

解题思路

固定长度的滑动窗口题目。我们可以维护一个窗口大小为 minutes 的滑动窗口。使用 window_count 记录当前窗口内生气的顾客人数。然后滑动求出窗口中最大顾客数,然后累加上老板未生气时的顾客数,就是答案。具体做法如下:

  1. ans 用来维护答案数目。window_count 用来维护窗口中生气的顾客人数。
  2. leftright 都指向序列的第一个元素,即:left = 0right = 0
  3. 如果书店老板生气,则将这一分钟的顾客数量加入到 window_count 中,然后向右移动 right
  4. 当窗口元素个数大于 minutes 时,即:right - left + 1 > count 时,如果最左侧边界老板处于生气状态,则向右移动 left,从而缩小窗口长度,即 left += 1,使得窗口大小始终保持为小于 minutes
  5. 重复 3 ~ 4 步,直到 right 到达数组末尾。
  6. 然后累加上老板未生气时的顾客数,最后输出答案。

代码

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        left = 0
        right = 0
        window_count = 0
        ans = 0

        while right < len(customers):
            if grumpy[right] == 1:
                window_count += customers[right]

            if right - left + 1 > minutes:
                if grumpy[left] == 1:
                    window_count -= customers[left]
                left += 1

            right += 1
            ans = max(ans, window_count)

        for i in range(len(customers)):
            if grumpy[i] == 0:
                ans += customers[i]
        return ans