发表于 2024.04.23

• 题目中带有”连续”、”只能使用一次”等字眼，说明可以尝试使用滑动窗口解决。首先计算老板不抑制情绪的情况下，原始的满意度orig_satisfied = sum(cnt * (1 - is_grumpy) for cnt, is_grumpy in zip(customers, grumpy))，然后使用一个大小为minutes的窗口，计算窗口下抑制情绪所能带来的满意度提升，然后不断向右滑动窗口找到满意度提升量的最大值，加上原始满意度返回即可。

  class Solution:
      def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
          n = len(customers)
          # 如果不抑制情绪, 原始的满意度
          orig_satisfied = sum(cnt * (1 - is_grumpy) for cnt, is_grumpy in zip(customers, grumpy))
          # 新建一个长度为minutes的滑动窗口[l, r]
          l, r = 0, minutes - 1
          # 窗口内抑制情绪, 满意度的提升量
          satisfied_increment_in_cur_window = 0
          for i in range(minutes):
              satisfied_increment_in_cur_window += customers[i] * grumpy[i]
          # 最大的满意度提升量
          max_increment = satisfied_increment_in_cur_window
          # 开始往右滑动窗口, 不断更新窗口内的满意度提升量
          while r + 1 < n:
              if grumpy[l]:
                  satisfied_increment_in_cur_window -= customers[l]
              l += 1
              r += 1
              if grumpy[r]:
                  satisfied_increment_in_cur_window += customers[r]
              max_increment = max(max_increment, satisfied_increment_in_cur_window)
          return orig_satisfied + max_increment

• LC 题目链接