前言

        欢迎大家积极在评论区留言发表自己的看法，知无不言，言无不尽，养成每天刷题的习惯，也可以自己发布优质的解题报告，供社区一同鉴赏，吸引一波自己的核心粉丝。
        今天是七月集训第六天：滑动窗口🔥🔥🔥

一、练习题目

        643. 子数组最大平均数 I
        718. 最长重复子数组
        978. 最长湍流子数组
        1052. 爱生气的书店老板

二、算法思路

• 1、643. 子数组最大平均数 I：🔥固定窗口大小的滑窗问题。

• 2、718. 最长重复子数组：🔥🔥🔥这道题思路不难，但是用暴力解法会超时，所以利用动态规划来进行优化。
  动态规划过程
  1. 定义状态
    dp[i][j] 代表以 nums1[i-1] 结尾和 nums2[j-1] 结尾构成的最长公共子数组的「长度」
    与定义 LCS 相同的是都需要将 dp 多申请一位，dp[0][j] 和 dp[i][0] 中的 0 代表不使用这个数组的数
    不同的是，需要记录的是「结尾」构成公共数组的长度，LCS 需要的是 nums1[0,i-1] 和 nums2[0,j-1] 「区间内」公共数组的长度
  2. 状态转移方程
    能够连续推导是否为「公共子数组」的两个条件是：当前两个元素是否相同；这两个元素前的子数组，是否是公共的
    因此，可以写出状态转移的过程：
    当前两元素「相等」，nums1[i-1] == nums2[j-1]
      前面是公共子数组，dp[i][j] = 前面子数组的长度 + 当前两个相同的元素
      前面不是公共子数组，当前位置的 dp[i][j] 只有当前两个相同元素构成公共子数组，也就是1
    当前两元素「不相等」，以这两个元素结尾构不成公共子数组，dp[i][j] 直接置为0
  3. 初始化
    dp[i][0] dp[0][j] 任意一个数组为空时，最长公共子数组长度为0
  4. 输出
    遍历的过程中，统计 dp[i][j] 的最大值

• 3、978. 最长湍流子数组：🔥利用两个数组进行线性枚举。

• 4、1052. 爱生气的书店老板：🔥🔥🔥五月做过一遍今天再来看一遍。
    重点：
      1、不生气时顾客会留下，生气时会赶走顾客。
      2、秘密技巧可以使老板在窗口大小 X 的时间内不生气。我们使用秘密技巧的原则是：寻找一个时间长度为 X 的窗口，能留住更多的原本因为老板生气而被赶走顾客。
      3、使用秘密技巧能得到的最终的顾客数 = 所有不生气时间内的顾客总数 + 在窗口 X 内使用秘密技巧挽留住的原本因为生气而被赶走顾客数。
    因此，可以把题目分为以下两部分求解：
      1、所有不生气时间内的顾客总数： i 遍历$[0,customers.length)$，累加$grumpy[i]==0$的customers[i]。
      2、在窗口 X 内因为生气而被赶走的顾客数：使用大小为 X 的滑动窗口，计算滑动窗口内的$grumpy[i]==1$的customers[i]，得到在滑动窗口内老板生气时对应的顾客数。
  leetcode题解有一位大佬的图画的特别好：传送门
  
  
  
  

三、源码剖析

// 643. 子数组最大平均数 I
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int l = 0, r = 0, sum = 0, ans = INT_MIN;
        while(r < nums.size()) {
            sum += nums[r];
            while(r - l + 1 > k) {
                sum -= nums[l];
                ++l;
            }
            if(r - l + 1 == k) {
                ans = max(ans, sum);
            }
            r++;
        }
        return ans *1.0 / k;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 1、用l和r指针维护一个k大小的窗口，r指针不断增加去求和，如果大于k那么l指针增加缩小窗口。当窗口大小刚好是k就更新一下最大值，最后返回平均值即可。

// 718. 最长重复子数组
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), ans = 0;
        int dp[1001][1001];
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(!i || !j) {
                    dp[i][j] = nums1[i] == nums2[j] ? 1 : 0;
                } else {
                    dp[i][j] = nums1[i] == nums2[j] ? dp[i - 1][j - 1] + 1 : 0;
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 1、过程写在思路了。

// 978. 最长湍流子数组
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int ans = 0;
        int aec[40010], des[40010]; //（1）
        for(int i = 0; i < arr.size(); ++i) {
            aec[i] = des[i] = 1;
            if(i) {
                if(arr[i] > arr[i - 1]) {
                    aec[i] = des[i - 1] + 1;
                }
                if(arr[i] < arr[i - 1]) {
                    des[i] = aec[i- 1] + 1;
                }
            }
            ans = max(ans, max(aec[i], des[i]));
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 1、aec代表了数组中元素是递增的最长序列长度，des代表了数组中元素是递增的最长序列长度；
• 2、举一个具体例子来说明：arr = [9,4,2,10,7,8,8,1,9]
  

// 1052. 爱生气的书店老板
class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int n = customers.size(), total = 0, sum = 0, ans;
        for(int i = 0; i < n; i++) {
            total += (!grumpy[i]) * customers[i]; //(1)
        }

        for(int i = 0; i < minutes; i++) {
            sum += grumpy[i] * customers[i]; //(2)
        }
        ans = sum;

        for(int i = minutes; i < n; i++) {
            sum -= grumpy[i - minutes] * customers[i - minutes];
            sum += grumpy[i] * customers[i];
            ans = max(ans, sum); //(3)
        }
        ans += total; //(4)
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 1、求出所有不生气时间内的顾客总数;
• 2、定窗口问题看以前直播的时候经常这么干，先求出前minutes个窗口的总和；
• 3、数组下标从minutes开始维护窗口的大小为minutes，不断求出使用技巧后能使得原来不满意顾客变成满意的数量，更新这个最大值；
• 4、把上述两种情况的顾客总数相加就是答案。