ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【leetcode--爱气愤的书店老板】 [打印本页]
作者: 怀念夏天    时间: 2024-6-28 15:30
标题: 【leetcode--爱气愤的书店老板】
解题思绪
重点：

不气愤时顾客会留下，气愤时会赶走顾客。
「秘密本领」可以使老板在窗口大小 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中））
  1. class Solution:
  2.     def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
  3.         N = len(customers)
  4.         sum_ = 0
  5.         # 所有不生气时间内的顾客总数
  6.         for i in range(N):
  7.             sum_ += customers[i] * (1 - grumpy[i])
  8.         # 生气的 X 分钟内，会让多少顾客不满意
  9.         curValue = 0
  10.         # 先计算起始的 [0, X) 区间
  11.         for i in range(X):
  12.             curValue += customers[i] * grumpy[i]
  13.         resValue = curValue
  14.         # 然后利用滑动窗口，每次向右移动一步
  15.         for i in range(X, N):
  16.             # 如果新进入窗口的元素是生气的，累加不满意的顾客到滑动窗口中
  17.             # 如果离开窗口的元素是生气的，则从滑动窗口中减去该不满意的顾客数
  18.             curValue = curValue + customers[i] * grumpy[i] - customers[i - X] * grumpy[i - X]
  19.             # 求所有窗口内不满意顾客的最大值
  20.             resValue = max(resValue, curValue)
  21.         # 最终结果是：不生气时的顾客总数 + 窗口X内挽留的因为生气被赶走的顾客数
  22.         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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4