今天，書店老板有一家店打算試營業(yè) customers.length 分鐘。每分鐘都有一些顧客（customers[i]）會(huì)進(jìn)入書店，所有這些顧客都會(huì)在那一分鐘結(jié)束后離開。在某些時(shí)候，書店老板會(huì)生氣。 如果書店老板在第 i 分鐘生氣，那么 grumpy[i] = 1，否則 grumpy[i] = 0。 當(dāng)書店老板生氣時(shí)，那一分鐘的顧客就會(huì)不滿意，不生氣則他們是滿意的。書店老板知道一個(gè)秘密技巧，能抑制自己的情緒，可以讓自己連續(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

解題思路

比較典型的滑動(dòng)窗口, 雙指針求解問題
首先提醒大家, 生氣不好, 好孩子不要學(xué)哦~

1.先計(jì)算初始用戶滿意度
2.依次循環(huán)找到, 每個(gè)區(qū)間變化的滿意度總數(shù), 并找到最大變化的滿意度總數(shù)
3.初始滿意度 + 最大變化的滿意度就是我們要找的結(jié)果

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 {

        // 定義最大變化數(shù), 初始總數(shù), 起止2個(gè)指針
        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 {

            // 定義滑動(dòng)區(qū)間變化初始值
            var temp = 0
            
            // 循環(huán)判斷滑動(dòng)窗口中的變化值
            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ù)滑動(dòng)
            last += 1
            next += 1
        }
        
        // 返回最大的滿意度
        return sum + maxsave
        
    }

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址