【leetcode--爱气愤的书店老板】
解题思绪重点：
不气愤时顾客会留下，气愤时会赶走顾客。
「秘密本领」可以使老板在窗口大小 X 的时间内不气愤。我们使用「秘密本领」的原则是：探求一个时间长度为 X 的窗口，能留住更多的原本因为老板气愤而被赶走顾客。
使用「秘密本领」能得到的最终的顾客数 = 所有不气愤时间内的顾客总数 + 在窗口 X 内使用「秘密本领」挽留住的原本因为气愤而被赶走顾客数。
因此，可以把标题分为以下两部分求解：
所有不气愤时间内的顾客总数：使用 iii 遍历==0grumpy == 0grumpy==0时的customerscustomerscustomers。
在窗口 X 内因为气愤而被赶走的顾客数：使用大小为 X 的滑动窗口，计算滑动窗口内的grumpy==1grumpy == 1grumpy==1时的customerscustomerscustomers，得到在滑动窗口内老板气愤时对应的顾客数。
滑动窗口遍历：
从第x个元素开始遍历到末了一个元素，每一步中，我们实行以下操作：
假如新进入窗口的元素（即customers和grumpy）对应的员工是气愤的就将其服务的顾客数加到curValue中。
假如脱离窗口的元素（即customers和grumpy对应的员工是气愤的，则从其服务的顾客数中减去该值（从curValue中））
class Solution:
def maxSatisfied(self, customers: List, grumpy: List, X: int) -> int:
N = len(customers)
sum_ = 0
# 所有不生气时间内的顾客总数
for i in range(N):
sum_ += customers * (1 - grumpy)
# 生气的 X 分钟内，会让多少顾客不满意
curValue = 0
# 先计算起始的 [0, X) 区间
for i in range(X):
curValue += customers * grumpy
resValue = curValue
# 然后利用滑动窗口，每次向右移动一步
for i in range(X, N):
# 如果新进入窗口的元素是生气的，累加不满意的顾客到滑动窗口中
# 如果离开窗口的元素是生气的，则从滑动窗口中减去该不满意的顾客数
curValue = curValue + customers * grumpy - customers * grumpy
# 求所有窗口内不满意顾客的最大值
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企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]