今天绳锅，書店老板有一家店打算試營業(yè) customers.length 分鐘捕发。每分鐘都有一些顧客（customers[i]）會進(jìn)入書店旭绒，所有這些顧客都會在那一分鐘結(jié)束后離開慧邮。在某些時候鞠评，書店老板會生氣猜拾。 如果書店老板在第 i 分鐘生氣大莫，那么 grumpy[i] = 1鳖悠，否則 grumpy[i] = 0烈炭。 當(dāng)書店老板生氣時溶锭，那一分鐘的顧客就會不滿意，不生氣則他們是滿意的梳庆。書店老板知道一個秘密技巧暖途，能抑制自己的情緒，可以讓自己連續(xù) X 分鐘不生氣膏执，但卻只能使用一次驻售。請你返回這一天營業(yè)下來，最多有多少客戶能夠感到滿意的數(shù)量更米。
例子
輸入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
輸出：16
解釋：
書店老板在最后 3 分鐘保持冷靜欺栗。
感到滿意的最大客戶數(shù)量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
其中
1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1
解題思路
比較典型的滑動窗口, 雙指針求解問題
首先提醒大家, 生氣不好, 好孩子不要學(xué)哦~
1.先計算初始用戶滿意度
2.依次循環(huán)找到, 每個區(qū)間變化的滿意度總數(shù), 并找到最大變化的滿意度總數(shù)
3.初始滿意度 + 最大變化的滿意度就是我們要找的結(jié)果
代碼
未翻譯版
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 {
// 定義最大變化數(shù), 初始總數(shù), 起止2個指針
var maxsave = 0, sum = 0, last = 0, next = X - 1
// 循環(huán), 找到初始滿意度總數(shù)
for i in 0..<customers.count {
// 0: 滿意, 1: 不滿意, 我們判斷0, 依次添加
if grumpy[i] == 0 {
sum = sum + customers[i]
}
}
// 雙指針查找新增的總數(shù)
while next < customers.count {
// 定義滑動區(qū)間變化初始值
var temp = 0
// 循環(huán)判斷滑動窗口中的變化值
for i in last...next {
// 不滿足:1全變瞞住, 找到窗口中對應(yīng)1下表的用戶值, 依次增加
if grumpy[i] == 1 {
temp += customers[i]
}
}
// 取每次循環(huán)的最大值
maxsave = max(temp, maxsave)
// last + 1, next + 1 繼續(xù)滑動
last += 1
next += 1
}
// 返回最大的滿意度
return sum + maxsave
}
題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址
