爱生气的书店老板 图解题解

这道题到底在问什么

输入

customers=[1,0,1,2,1,1,7,5], grumpy=[0,1,0,1,0,1,0,1], minutes=3

输出

16

最优解：一步一步想明白

1. 3记住「绿色白赚记 base，红色用一个宽 minutes 的窗口挑挽回最多的一段」，下面每帧都在套它。
2. 4先给每分钟上色：绿色是老板不生气的分钟（顾客白白满意），红色是生气的分钟（顾客流失）。技巧能连续盖住 3 分钟，把这段窗口内红色分钟的损失抢回来。
3. 5第 0 分钟绿色（不生气），1 位顾客白赚，base 累加到 1。
4. 6第 1 分钟红色（生气），0 位顾客流失，先不计入 base——等会儿看技巧能不能盖到它。
5. 7第 2 分钟绿色（不生气），1 位顾客白赚，base 累加到 2。
6. 8第 3 分钟红色（生气），2 位顾客流失，先不计入 base——等会儿看技巧能不能盖到它。
7. 9第 4 分钟绿色（不生气），1 位顾客白赚，base 累加到 3。
8. 10第 5 分钟红色（生气），1 位顾客流失，先不计入 base——等会儿看技巧能不能盖到它。
9. 11第 6 分钟绿色（不生气），7 位顾客白赚，base 累加到 10。
10. 12第 7 分钟红色（生气），5 位顾客流失，先不计入 base——等会儿看技巧能不能盖到它。
11. 13把冷静技巧盖在第 0~2 分钟（高亮窗口）。这段里原本生气流失的顾客被挽回，共 0 位。
12. 140 没超过当前最优 best = 0，窗口继续右滑。
13. 15把冷静技巧盖在第 1~3 分钟（高亮窗口）。这段里原本生气流失的顾客被挽回，共 2 位。
14. 162 比之前最优更高，刷新 best = 2，记下窗口起点 1。
15. 17把冷静技巧盖在第 2~4 分钟（高亮窗口）。这段里原本生气流失的顾客被挽回，共 2 位。
16. 182 没超过当前最优 best = 2，窗口继续右滑。
17. 19把冷静技巧盖在第 3~5 分钟（高亮窗口）。这段里原本生气流失的顾客被挽回，共 3 位。
18. 203 比之前最优更高，刷新 best = 3，记下窗口起点 3。
19. 21把冷静技巧盖在第 4~6 分钟（高亮窗口）。这段里原本生气流失的顾客被挽回，共 1 位。
20. 221 没超过当前最优 best = 3，窗口继续右滑。
21. 23把冷静技巧盖在第 5~7 分钟（高亮窗口）。这段里原本生气流失的顾客被挽回，共 6 位。
22. 246 比之前最优更高，刷新 best = 6，记下窗口起点 5。
23. 25最优是把冷静技巧盖在第 5~7 分钟，挽回 6 位。加上白赚的 base 10，最多满意顾客 = 16。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        base = sum(c for c, g in zip(customers, grumpy) if g == 0)
        extra = best = 0
        for i, c in enumerate(customers):
            if grumpy[i]:
                extra += c
            if i >= minutes and grumpy[i - minutes]:
                extra -= customers[i - minutes]
            best = max(best, extra)
        return base + best

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int base = 0, extra = 0, best = 0;
        for (int i = 0; i < (int)customers.size(); ++i) {
            if (!grumpy[i]) base += customers[i];
            if (grumpy[i]) extra += customers[i];
            if (i >= minutes && grumpy[i - minutes]) extra -= customers[i - minutes];
            best = max(best, extra);
        }
        return base + best;
    }
};

import java.util.*;

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int base = 0, extra = 0, best = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) base += customers[i];
            if (grumpy[i] == 1) extra += customers[i];
            if (i >= minutes && grumpy[i - minutes] == 1) extra -= customers[i - minutes];
            best = Math.max(best, extra);
        }
        return base + best;
    }
}

复杂度

面试官可能追问