解题思绪
重点：
不气愤时顾客会留下，气愤时会赶走顾客。
「秘密本领」可以使老板在窗口大小 X 的时间内不气愤。我们使用「秘密本领」的原则是：探求一个时间长度为 X 的窗口，能留住更多的原本因为老板气愤而被赶走顾客。
使用「秘密本领」能得到的最终的顾客数 = 所有不气愤时间内的顾客总数 + 在窗口 X 内使用「秘密本领」挽留住的原本因为气愤而被赶走顾客数。
因此，可以把标题分为以下两部分求解：
所有不气愤时间内的顾客总数：使用 iii 遍历[0,customers.length)[0, customers.length)[0,customers.length)，累加grumpy==0grumpy == 0grumpy==0时的customerscustomerscustomers。
在窗口 X 内因为气愤而被赶走的顾客数：使用大小为 X 的滑动窗口，计算滑动窗口内的grumpy==1grumpy == 1grumpy==1时的customerscustomerscustomers，得到在滑动窗口内老板气愤时对应的顾客数。
滑动窗口遍历：
从第x个元素开始遍历到末了一个元素，每一步中，我们实行以下操作：
假如新进入窗口的元素（即customers和grumpy）对应的员工是气愤的就将其服务的顾客数加到curValue中。
假如脱离窗口的元素（即customers[i-X]和grumpy[i-X]对应的员工是气愤的，则从其服务的顾客数中减去该值（从curValue中））
- class Solution:
- def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
- N = len(customers)
- sum_ = 0
- # 所有不生气时间内的顾客总数
- for i in range(N):
- sum_ += customers[i] * (1 - grumpy[i])
- # 生气的 X 分钟内，会让多少顾客不满意
- curValue = 0
- # 先计算起始的 [0, X) 区间
- for i in range(X):
- curValue += customers[i] * grumpy[i]
- resValue = curValue
- # 然后利用滑动窗口，每次向右移动一步
- for i in range(X, N):
- # 如果新进入窗口的元素是生气的，累加不满意的顾客到滑动窗口中
- # 如果离开窗口的元素是生气的，则从滑动窗口中减去该不满意的顾客数
- curValue = curValue + customers[i] * grumpy[i] - customers[i - X] * grumpy[i - X]
- # 求所有窗口内不满意顾客的最大值
- resValue = max(resValue, curValue)
- # 最终结果是：不生气时的顾客总数 + 窗口X内挽留的因为生气被赶走的顾客数
- return sum_ + resValue
参考链接：https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/616238/yong-mi-mi-ji-qiao-wan-liu-zhu-zui-duo-d-py41/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
