image.png

思路：滑动窗口

  • 分成2部分，第一，记录原有的客户总量all_customers；第二，找到最大的增加量increase_customers，然后计算二者总和即可。
  • 问题关键在于，如何寻找最大的增量：可以使用滑动窗口的思想
  • 滑动窗口还是分成两部分，第一，找到第一个窗口并计算。第二，将这个窗口向后滑动，每一次扔掉一个左边的数据，加上一个右边的数据，不断更新，直到找到max_increase_customers

代码：

  1. class Solution {
  2. public:
  3.     int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
  4.         int all_customers = 0, num_customers = customers.size();
  6.         // 记录原有的客户数量
  7.         for (int i = 0; i < num_customers; ++i) {
  8.             all_customers += ((!grumpy[i]) * customers[i]);
  9.         }
  11.         // 统计增加量
  12.         int increase_customers = 0; 
  13.         for (int i = 0; i <= minutes - 1; ++i) {
  14.             increase_customers += grumpy[i] * customers[i];
  15.         }
  17.         // 滑动窗口
  18.         int max_increase_customers = increase_customers;
  19.         for (int left = 1, right = minutes; right < num_customers; ++right, ++left) {
  20.             increase_customers -= (grumpy[left - 1] * customers[left - 1]);
  21.             increase_customers += (grumpy[right] * customers[right]);
  22.             max_increase_customers = max(max_increase_customers, increase_customers);
  23.         }
  25.         return all_customers + max_increase_customers;
  26.     }
  27. };