今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
例子
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
其中
1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1
解题思路
比较典型的滑动窗口, 双指针求解问题
首先提醒大家, 生气不好, 好孩子不要学哦~
1.先计算初始用户满意度
2.依次循环找到, 每个区间变化的满意度总数, 并找到最大变化的满意度总数
3.初始满意度 + 最大变化的满意度就是我们要找的结果
1.png
2.png
3.png
4.png
5.png
6.png
7.png
代码
未翻译版
func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ X: Int) -> Int {
var maxsave = 0, sum = 0, last = 0, next = X - 1
for i in 0..<customers.count {
if grumpy[i] == 0 {
sum = sum + customers[i]
}
}
while next < customers.count {
var temp = 0
for i in last...next {
if grumpy[i] == 1 {
temp += customers[i]
}
}
maxsave = max(temp, maxsave)
last += 1
next += 1
}
return sum + maxsave
}
翻译版
func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ X: Int) -> Int {
// 定义最大变化数, 初始总数, 起止2个指针
var maxsave = 0, sum = 0, last = 0, next = X - 1
// 循环, 找到初始满意度总数
for i in 0..<customers.count {
// 0: 满意, 1: 不满意, 我们判断0, 依次添加
if grumpy[i] == 0 {
sum = sum + customers[i]
}
}
// 双指针查找新增的总数
while next < customers.count {
// 定义滑动区间变化初始值
var temp = 0
// 循环判断滑动窗口中的变化值
for i in last...next {
// 不满足:1全变瞒住, 找到窗口中对应1下表的用户值, 依次增加
if grumpy[i] == 1 {
temp += customers[i]
}
}
// 取每次循环的最大值
maxsave = max(temp, maxsave)
// last + 1, next + 1 继续滑动
last += 1
next += 1
}
// 返回最大的满意度
return sum + maxsave
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
