LeetCode上爱生气的书店老板,题目写的花里胡哨,但是内核还是滑动数组,记录下解题思路
题意是:
customers
数组表示每分钟会来的客人
grumpy
数组表示老板什么时候生气,1表示生气,0表示不生气
X
是老板能连续多少分钟不生气
生气的时候客人不满意,需要求老板什么时候不生气能够拥有更多的客人满意度
假设传入customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
,可以绘制出如下表格
已知的是,当
grumpy[i] = 0
的时候用户是满意的那么最大满意度人数 = 不生气的时候客户数 + X区间内最大的客户数
不生气时候客户数 = 所有grumpy[i] = 0时候的用户数之和
X区间内最大的客户数 = 除去grumpy[i] = 0时候的用户数的数组,在X区间内的最大值
这个X区间是已知大小的,在处理后的
customers
数组上进行滑动窗口操作,求最大值即可
所以做以下操作:
- 处理
customers
数组,求出不生气时候的客户数,以及剔除不生气时候的客户数
用customers[i] * grumpy[i]
来获得处理后的newcustomers
数组,并且当grumpy[i] = 0
的时候,把对应的customers[i]
的值放入结果中
此时不生气时候的客户数为 = 1 + 1 + 1 + 7 = 10 - 用滑动窗口处理
newcustomers
此时对应的窗口大小X = 3
不停移动窗口求窗口内所有数的和,最后可得
在这种情况内窗口内数字之和最大
所以**X区间内最大的客户数 = 1 + 0 + 5 = 6 **
那么最后返回的结果就是res = 不生气时候的客户数为 + X区间内最大的客户数 = 10 + 6 = 16
var maxSatisfied = function(customers, grumpy, X) {
// 定义处理过后的newCustomers
let newCustomers = new Array(customers.length).fill(0)
// 设置窗口的左右
let left = 0
let right = 0
// 当前窗口内的最大客户数
let max = Number.MIN_VALUE
// 当前窗口内的客户数
let window = 0
// 不生气时候的客户数
let c = 0
// 开始处理customers
for(let i = 0; i < customers.length;i++) {
// 当grumpy[i] = 0的时候就是不生气,当前的customers[i]要保存
if(grumpy[i] === 0) c += customers[i]
// 通过customers[i] * grumpy[i]得到newCustomers[i]
newCustomers[i] = customers[i] * grumpy[i]
}
// 对newCustomers进行滑动窗口处理
while(right < newCustomers.length) {
// 当窗口数大于X的时候就要left++
if(right - left + 1 > X) {
// 将之前的left的值从window中减去
window -= newCustomers[left]
// left右移
left++
}
// 保存当前的newCustomers[right]
window += newCustomers[right]
// 判断窗口内的当前数和 窗口内的最大数之间谁大
max = Math.max(window,max)
// 窗口扩展
right++
}
// 最后返回max+c的结果
return max + c
};