Loading... > https://leetcode.cn/problems/grumpy-bookstore-owner/description/?envType=daily-question&envId=2024-04-11 书店老板可以抑制自己 $minutes$ 分钟不生气，但只能用一次。也就是需要找出损失满意度最多且连续的 $minutes$ 分钟，很容易想到使用滑动窗口。 题目要求一天有多少客户能满意，其中包含两部分：老板不生气时候的顾客；老板生气但抑制情绪时候的顾客。第一部分只需要统计 $grumpy$ 为 $0$ 时候的顾客数即可，第二部分则通过滑动窗口求解： ```c++ class Solution { public: int maxSatisfied(std::vector<int>& customers, std::vector<int>& grumpy, int minutes) { const int n = customers.size(); int baseSatisfied = 0, curSuppressed = 0; for (int i = 0; i < minutes; i++) grumpy[i] == 0 ? baseSatisfied += customers[i] : curSuppressed += customers[i]; int maxSuppressed = curSuppressed; for (int end = minutes; end < n; end++) { grumpy[end] == 0 ? baseSatisfied += customers[end] : curSuppressed += customers[end]; if (grumpy[end - minutes]) curSuppressed -= customers[end - minutes]; if (curSuppressed > maxSuppressed) maxSuppressed = curSuppressed; } return baseSatisfied + maxSuppressed; } }; ``` - 时间复杂度 $O(n)$ ，其中 $n$ 为数组 $customers$ 的长度。 - 空间复杂度 $O(1)$ 。 最后修改：2024 年 05 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏