力扣leetcode1052. 爱生气的书店老板C++

力扣leetcode1052. 爱生气的书店老板C++

leetcode1052. 爱生气的书店老板C++

思路

这道题目初见可能没有思路，注意观察题目 老板可以在连续X分钟内不生气 求解最大的客户数量从这些关键词我们可以联想到滑动窗口
当采用滑动窗口时 题目已经给出了固定的窗口大小X
那么通过窗口大小我们可以很自然地将数组分为3个部分，左半边部分 窗口部分， 右半部分
那么我们先计算初始三部分的顾客数量 然后通过移动窗口 重新计算顾客数量 最终求解问题

C++代码如下

class Solution {
public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {//l利用滑动窗口的思想对问题进行求解//首先我们已知老板在X个连续区间内不会生气//因此我们呢可以把区间划分为3部分//即 左 中 右三部分//那么问题就转化为求解这三部分和的最大值int left = 0;int right = left+X;//初始情况下 左半部分int sum_left = 0;int sum_mid = 0;int sum_right = 0;int sum = 0;int n = customers.size();//计算初始和//左半部分和for(int i = 0; i < left; ++i){if(grumpy[i] == 0){sum_left += customers[i];}}//中间部分和for(int i = left; i < right; ++i){sum_mid += customers[i];}//右半部分和for(int i = right; i < n; ++i){if(grumpy[i] == 0){sum_right += customers[i];}}sum = sum_left + sum_mid + sum_right;for(; right < n;){int res = 0;if(grumpy[left] == 0){sum_left += customers[left];}//相当于窗口前移一次sum_mid -= customers[left];if(grumpy[right] == 0){sum_right -= customers[right];}sum_mid += customers[right];res = sum_left + sum_mid + sum_right;sum = max(res, sum);left++;right++;}return sum;}
};