leetcode1052--爱生气的书店老板

本文主要是介绍leetcode1052--爱生气的书店老板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

给定一个消费者时间序列和书店老板生气的序列，再给一段书店老板可以控制生气的最大时间段；求最多能使得多少消费者满意。

2. 题解

滑动窗口问题，对于老板不生气的时间点的消费者，他们都满意；

把他们都加上，就变成了一个标准的滑动窗口问题。

2.1 代码一

class Solution {
public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {int ans = 0;int sz = customers.size();for (int i = 0;i < sz; ++i) {if (!grumpy[i])ans += customers[i],customers[i] = 0;}int mx = 0;int cnt = 0;for (int i = 0;i < sz; ++i) {cnt += customers[i];if (i >= minutes) {cnt -= customers[i - minutes];}mx = max(cnt, mx);}return ans + mx; }
};作者：宫水三叶
链接：https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/616352/hua-dong-chuang-kou-luo-ti-by-ac_oier-nunu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.2 我的

class Solution {
public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {// 先求不满意的人数int ans = 0;queue<int> not_in;int sz = customers.size();int mx = 0;int cnt = 0;for (int i = 0; i < sz; ++i) {if ( customers[i] && !grumpy[i] ) {ans += customers[i];}else if ( customers[i] && grumpy[i] ){mx = max(cnt, mx);not_in.push(i);int front = not_in.front();cnt += customers[i];while (i - front + 1 > minutes) {cnt -= customers[front];not_in.pop();front = not_in.front();}}}mx = max(cnt, mx);return ans + mx; }
};