JZX轻语：简
LeetCode 1052 - 爱生气的书店老板
发表于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