滑动窗口——leetcode题解

1052. 爱生气的书店老板

思路：先求出来不生气的时候总人数是多少，然后用滑动窗口求出来在生气的时候那个区间因为生气而不满意的人数的最大值，把这个最大值记录下来然后返回的时候，满意的人数加上这个不满意的最大值就是答案。

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int size = customers.size();
        int l = 0,r = 0;
        int e = 0;
        int tmp = 0;
        int ans = 0;
        while(r<size)
        {
            if(grumpy[r]==0) ans+=customers[r];
            tmp+=grumpy[r]*customers[r];
            r++;
            e = max(e,tmp);

            if(r-l==minutes) tmp-=grumpy[l]*customers[l++];
        }
        return ans+e;
    }
};

643. 子数组最大平均数 I

思路：先第一层for循环求出来初始窗口的子数组的平均值，然后向后循环移动窗口，不断求出平均值，最后留下最大值就可以了。

double findMaxAverage(int* nums, int numsSize, int k){
    
    double max = 0;
    double sum = 0;
    for(int i = 0;i<k;i++)
    {
    
        sum+=nums[i];
    }
    max = sum;
    for(int i =k;i<numsSize;i++)
    {
    
        sum = sum - nums[i-k] + nums[i];
        max = (max>sum)?max:sum;
    }
    return max/k;
}

718. 最长重复子数组

思路：滑动窗口，题解的某位大神提供的尺取法滑动窗口将两个数组，先让长度较小的数组成为数组a，然后让a这个尺子不动移动b尺子，每次比较尺子重叠部分的最长公共子数组
第一阶段：第一次b数组的最后一个元素和a数组的第一个元素，然后不断移动，知道b数组中第bn-an个元素和a数组全部比较完毕后，第一阶段结束。
第二阶段：假设b数组比a数组长，那此时在a数组前面还要一部分长度的b数组，也就是bn-an从这位置开始，向后移动b数组，比较的长度还是an，直到b数组从0，到an位置全部比较完毕。
第三阶段：b数组与a数组的重叠开始减少，直到最后b数组的第一个元素和a数组的最后一个元素重叠，这是最后一次比较。
比较使用的函数 cmplen ，第一个参数就是a数组，i表示a数组开始比较的位置，然后是b数组，j表示b数组开始比较的起始位置，最后一个参数len表示要比较的这个区间的长度是多长。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        return nums1.size()<nums2.size() ? findMax(nums1,nums2) : findMax(nums2,nums1);
    }

    int findMax(vector<int>& a,vector<int>&b)
    {
        int an = a.size(),bn = b.size();
        int maxlen = 0;
        for(int len = 1; len<=an;len++)
            maxlen = max(maxlen,cmplen(a,0,b,bn-len,len));
        for(int j = bn-an;j>=0;j--)
            maxlen = max(maxlen,cmplen(a,0,b,j,an));
        for(int i = 1;i<an;i++)
            maxlen = max(maxlen,cmplen(a,i,b,0,an-i));
        return maxlen;
    }

    int cmplen(vector<int>& a,int i,vector<int>& b,int j,int len)
    {
        int count = 0,maxlen = 0;
        for(int k = 0;k<len;k++)
        {
            if(a[i+k] == b[j+k])
                count++;
            else if(count>0)
            {
                maxlen = max(maxlen,count);
                count = 0;
            }
        }
        return count == 0? maxlen : max(maxlen,count);
    }
};

978. 最长湍流子数组

滑动窗口思想：如果一个元素arr[r] > arr[ r-1 ] && arr[r ] >arr[r+1]那么这个点就是合法的点，可以放进滑动窗口，然后++r，反之如果是小于号也是一样的。这样就是大于和小于交替出现。
对于特殊情况的判断，如果l==r的时候遇到一连串相等的时候就需要同时向后移动l和r直到出现不相等的时候，移动r形成滑动窗口，然后根据上面的条件判断就可以了。

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        int ans = 1;
        int l = 0,r = 0;
        while(r<n-1)
        {
            if(l==r)
            {
                if(arr[r] == arr[r+1])
                {
                    l++;
                }
                r++;
            }
            else
            {
                if(arr[r]>arr[r-1] && arr[r]>arr[r+1])
                    r++;
                else if(arr[r]<arr[r-1] && arr[r]<arr[r+1])
                    r++;
                else 
                    l = r;
            }
            ans = max(ans,r-l+1);
        }
        return ans;
    }
};