滑动窗口/双指针系列（1）_使用双指针滑动窗口法统计窗口内数字的个数,达到阈值时统计子数组个数

模板总结

《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。

我分享一个滑动窗口的模板，能解决大多数的滑动窗口问题：

def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目要求可能会改成求和/计数等
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]不符合题意：# 此时需要**一直移动**左指针，**直至找到**一个符合题意的区间,**注意是while不是if**
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

滑动窗口中用到了左右两个指针，它们移动的思路是：

以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

1. 定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；
2. 第一重while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right指针的求和/计数；
3. 第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left每次移动到了新位置，需要减少 left 指针的求和/计数；
4. 在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。
5. right指针每次向右移动一步，开始探索新的区间。

模板中的 sums 需要根据题目意思具体去修改，若是求和题目就把sums 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sums 。

另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间[left, right]不符合题意 。对于下面1208题而言，就是该区内的和 sums 超过了 maxCost 。

例题

leetcode424. 替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 104。

解析

如果一个问题暂时没有思路，可以先考虑暴力解法（不一定要实现）。当前问题的暴力解法是：枚举输入字符串的 所有 子串，对于每一个子串：

• 如果子串里所有的字符都一样，就考虑长度更长的子串；
• 如果当前子串里出现了至少两种字符，要想使得替换以后所有的字符都一样，并且重复的、连续的部分更长，应该替换掉出现次数最多字符 以外 的字符。

暴力解法的缺点：

• 做了重复的工作，子串和子串有很多重合的部分，重复扫描它们是不划算的；
• 做了很多没有必要的工作：

1. 如果找到了一个长度为 L 且替换 k个字符以后全部相等的子串，就没有必要考虑长度小于等于 L 的子串，因为题目只让我们找到符合题意的最长的长度；
2. 如果找到了一个长度为 L且替换 k 个字符以后不能全部相等的子串，左边界相同、长度更长的子串一定不符合要求（原因我们放在最后说）。

优化暴力解法，我们须要研究一些典型的例子并结合题意找到思路。

如: s = “AABABBA”, k = 1

max 记录窗口内相同字符最多的次数

遍历字符串, 窗口往右扩张 一旦 窗口大小 大于 max + k, 则窗口左边收缩 (窗口内可替换 k个其他字符 为 出现最多的字符)

  窗口扩张: left: 0, right: 0, 窗口: [ A ]ABABBA 
  窗口扩张: left: 0, right: 1, 窗口: [ AA ]BABBA 
  窗口扩张: left: 0, right: 2, 窗口: [ AAB ]ABBA 
  窗口扩张: left: 0, right: 3, 窗口: [ AABA ]BBA 
  移动左边: left: 1, right: 4, 窗口: A[ ABAB ]BA
  移动左边: left: 2, right: 5, 窗口: AA[ BABB ]A 
  移动左边: left: 3, right: 6, 窗口: AAB[ ABBA ] 
1
2
3
4
5
6
7

遍历完后, 只要看窗口大小即可

整个过程，我们使用了两个表示边界的变量，一前一后，交替在字符串上前进：右边界先向右和移动，直到它不能移动了为止，左边界再继续向右移动，整个过程像极了一个滑动的窗口在一条线段上移动。

我们还一直关心的是：考虑的子串中最多出现的字符是次数，因此须要一个频数数组，记录每个字符出现的次数。

方法：双指针（滑动窗口） 右边界先移动找到一个满足题意的可以替换 k个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> counts(26, 0);//记录当前窗口中每个字母出现的次数
        int left = 0, right = 0, maxCount = 0;// maxCount记录字符出现次数最多那个字符的次数

        while(right < s.length()){
            counts[s[right] - 'A']++;
            maxCount = max(maxCount, counts[s[right] - 'A']);
            // 若当前窗口大小 减去 窗口中最多相同字符的个数 大于 k 时,窗口右移一位，相应的左边界的字母个数-1
            if(right - left + 1 - maxCount > k){
                counts[s[left] - 'A']--;// 将窗口最左边的字符 在计数数组中减1
                left++;// 整个窗口右移一位
            }
            right++;
        }
        return right - left;//窗口大小即为最长长度，此处不用+1，因为上面while循环结束后right会多+1
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

同类问题

「力扣」第 1004 题：最大连续 1 的个数 III；
「力扣」第 1208 题：尽可能使字符串相等；
「力扣」第 1493 题：删掉一个元素以后全为 1 的最长子数组。

「滑动窗口」是一类使用「双指针」技巧，通过两个变量在数组上同向交替移动解决问题的算法。
这一类问题的思考路径通常是：先思考暴力解法，分析暴力解法的缺点（一般而言暴力解法的缺点是重复计算），然后结合问题的特点，使用「双指针」技巧对暴力解法进行剪枝。因此，思考算法设计的合理性是更关键的，这一点适用于所有算法问题。

练习

「力扣」第 3 题：无重复字符的最长子串；
「力扣」第 209 题：长度最小的子数组；
「力扣」第 76 题：最小覆盖子串；
「力扣」第 438 题：找到字符串中所有字母异位词；
「力扣」第 567 题：字符串的排列。

leetcode480. 滑动窗口中位数

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

[2,3,4]，中位数是 3 [2,3]，中位数是 (2 + 3) / 2 = 2.5 给你一个数组 nums，有一个长度为 k
的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1
位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

该题描述很直白，要解决不难，可以直接暴力取每个窗口值排序取中位数，此处略去代码。但遇到大量输入数据会超时。
难就难在如何利用数据结构+算法去优化，此处提供两种思路，法2更优。

法1.multiset

思路

怎么快速求中位数呢？为了降低时间复杂度的一个绝招就是空间换时间：利用更好的数据结构。是的，我们的目的是快速让一组数据有序，那就寻找一个内部是有序的数据结构呗！下面我分语言讲解一下常见的内部有序的数据结构。

• 在 C++ 中 set/multiset 是有序的集合，它们是基于红黑树实现的。其中 set 会对元素去重，而 multiset 可以有重复元素。
• 在 Java 中 TreeSet 是有序的集合，它也是基于红黑树实现的。 TreeSet 会对元素去重。
• 在 Python 中 heapq 实现了堆的算法，它不会对元素去重。 当频繁的插入和删除元素时，这些有序的数据结构能够在在 O(log(k))
  的时间复杂度内维护结构的有序性。但是对于红黑树实现的数据结构来说，不能做随机读取，因此获取中位数的时候，也只能通过 O(k)
  时间复杂度的查找。

1. 首先定义了结果数组 res 和 multiset；
2. 遍历输入中的每个元素；
3. 如果 multiset 中的元素超过了 k 个，需要把滑动窗口最左边 i - k 位置元素从 multiset 中删除（multiset 自动维护有序性）；
4. 把遍历到的当前元素插入到 multiset 中（multiset 自动维护有序性）；
5. 如果当前的位置达到了下标 k - 1，说明滑动窗口中有 k 个元素，开始求滑动窗口的中位数。

我们知道，如果数组 A 长度 k 是奇数时，令 mid = k / 2 ，那么中位数元素是 A[mid] ；如果数组长度 k为偶数时，那么中位数是 (A[mid] + A[mid - 1]) / 2 。为了适应奇数和偶数长度，可以用通用的表达式 (A[mid] +A[mid - (1 - k % 2)]) / 2来求中位数。

求 multiset 里的中位数：我们先求 multiset 中所有元素的起始位置（最小元素），然后在此基础上让指针走 k / 2 步得到mid ，最终 (A[mid] + A[mid - (1 - k % 2)]) / 2 就是我们要求的中位数。

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        multiset<double> mst;//multiset维护窗口内数字有序性O(log(k)),但无法快速查找，必须迭代器偏移，O(k)
        vector<double> ans;
        //模拟滑动窗口，满k个后，左边出，右边进
        for(int i = 0; i < n; i++){//i为右边界
            if(mst.size() >= k) mst.erase(mst.find(nums[i - k]));//删除左边的数
            mst.insert(nums[i]);//加入右边的数
            if(i >= k -1){
                multiset<double>::iterator mid = mst.begin();
                std::advance(mid, k / 2);//迭代器偏移到中间位置
                ans.push_back((*mid + *prev(mid, (1 - k % 2))) / 2);//根据k%2 - 1来统一奇偶两种情况的中位数计算
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

法2.双顶堆

本题考查动态维护数组的中位数。
我们思考中位数的性质：如果一个数是中位数，那么在这个数组中，大于中位数的数目和小于中位数的数目，要么相等，要么就相差一。
因此，我们采用对顶堆的做法，控制所有小于等于的数字放到一个堆中，控制所有比中位数大的数字放到另一个堆中，并且保证两个堆的数目相差小于等于1。这样就可以保证每一次查询中位数的时候，答案一定出于两个堆的堆顶元素之一。
因此选定数据结构：优先队列。因为优先队列采用的是堆结构，正好符合我们的需求。我们将所有小于等于中位数的元素放到small堆中（是一个大顶堆），将所有大于中位数的元素放到big堆中（是一个小顶堆）。

1. 初始化方法如下：

   将前K个元素全部插入到small堆中。从small堆中弹出K/2个元素到big堆中。
   这样，当K为奇数，则small堆元素比big堆元素多1；当K为偶数，两个堆元素相等。

2. 取中位数的操作：

   我们的插入操作可以保证每次优先插入到small堆中，因此small堆中的元素个数大于等于big堆的元素个数。

   • 当K为奇数时候，中位数是元素数量较多的small堆 堆顶元素。
   • 当K为偶数时候，中位数是small堆和big堆的堆顶元素平均值。

3. 窗口滑动过程中的操作：

   假定在上一次滑动之后，已经有small堆和big堆元素数目相差小于等于1. 设置当前的滑动时，假设balance =0。balance表示small堆元素数目减去big堆元素个数。 删除窗口左侧的元素。
   由于堆无法直接删除掉某个指定元素，先欠下这个账，等某次元素出现在堆顶的时候，再删除他。mp记录这个元素欠账的个数。mp[left]++;
   虽然没有真的在堆数据结构中删除窗口最左侧的元素，但是在我们的心中已经删掉他了。堆两侧的平衡性发生了变化。

   • 如果left<=small.top()，就说明删掉的元素在small堆中，我们让balance–;
   • 否则，就说明删掉的元素在big堆中，让balance++;

   添加进来窗口右侧的元素：

   • 如果right<=small.top()，就应该让这个元素放到samll堆里面，balance++；
   • 否则放到big堆里，balance–。

4. 经过上面的操作，balance要么为0，要么为2，要么为-2。我们需要经过调整使得balance为0。

   • 如果balance为0，在这次窗口滑动之前已经是平衡的，这次调整也没有让两堆的数目变化，所以不用调整两边的堆。
   • 如果balance为2，就说明small堆的元素比big堆的元素多了两个。从small堆减少一个，big堆里增加一个，就可以让两边相等。big.push(small.top());small.pop();
   • 如果balance为-2，就说明big堆的元素比small堆的元素多了两个。从big堆减少一个，small堆里增加一个，就可以让两边相等。small.push(big.top());big.pop();

5. 调整完了，现在该欠债还钱了。不能让那些早该删除的元素涉及到中位数的运算。

   分别检查两边的堆顶元素，如果堆顶元素欠着债，则弹出堆顶元素，直到堆顶元素没有欠债为止。
   有朋友问了：堆顶下面也有欠债的怎么办呢？我们之前说过，取中位数的时候只与堆顶元素有关，至于那些堆顶下面欠着债的，欠着就欠着吧，等他们到堆顶的时候再弹出去就好了。

6. 最后，添加中位数即可。

class Solution {
public:
    //两个堆各维护一半窗口内的数，那么中位数则在两个堆顶元素中得到
    priority_queue<int> small;//默认大顶堆
    priority_queue<int, vector<int>, greater<int>> big;//小顶堆
    unordered_map<int, int> mp;//记录延迟删除的数

    //返回中位数
    double get(int& k){
        if(k % 2) return small.top();//奇数个
        else return ((long)small.top() + big.top()) * 0.5;//偶数个
    }

    //主要来初始化并按规则维护两个堆
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        //1.初始化：窗口中一半数在small中，一半在big中，且small个数>=big的个数
        for(int i = 0; i < k; i++){small.push(nums[i]);}
        for(int i = 0; i < k / 2; i++){big.push(small.top()); small.pop();}
        vector<double> ans{get(k)};//答案数组，且存入第一个中位数

        //2.滑动窗口，并维护两个堆
        for(int i = k; i < nums.size(); i++){
            int balance = 0;//表示small堆元素数目减去big堆元素个数,假设当前为0
            int l = nums[i - k];//当前要移除窗口的数
            mp[l]++;//因为priority_queue不好直接删除，此处标记一下后面到堆顶再删除
            //判断移除的数在哪，更新balance
            if(!small.empty() && l <= small.top()){balance--;}//移除的数在small中
            else{balance++;}
            //判断加入的数在哪，更新balance,加该数入堆
            if(!small.empty() && nums[i] <= small.top()){
                small.push(nums[i]);
                balance++;
            }else{
                big.push(nums[i]);
                balance--;
            }
            //根据balance的值(0,-2,2三种)调整两个堆的元素个数
            if(balance > 0){//small元素个数过多
                big.push(small.top());
                small.pop();
            }
            if(balance < 0){//big中多
                small.push(big.top());
                big.pop();
            }
            //延迟删除：若被标记要删除的数到了堆顶，就删除掉,记得是while不是if
            while(!small.empty() && mp[small.top()] > 0){
                mp[small.top()]--;
                small.pop();
            }
            while(!big.empty() && mp[big.top()] > 0){
                mp[big.top()]--;
                big.pop();
            }
            //窗口滑一次维护完两个堆，就找一次中位数
            ans.push_back(get(k));
        }
        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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

leetcode1208. 尽可能使字符串相等

给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

思路

两个长度相等字符串的 s 和 t ，把 i 位置的 s[i] 转成 t[i] 的开销是两者 ASCII
码之差的绝对值。题目给出了允许的最大预算 maxCost ，求不超过预算的情况下能够转换的最长子串。

比如，对于 s = “abcd”, t = “bcdf”, cost = 3 而言，我们使用 costs[i] 表示从 s[i] 转成
t[i] 的开销，那么 costs = [1, 1, 1, 2] 。由于 maxCost = 3， 所以最多允许其前面三个字符进行转换。

于是题目变成了：已知一个数组 costs ，求：和不超过 maxCost 时最长的子数组的长度。

上面的表达方式跟题目是等价的。对题目抽象之后，是不是跟昨天的每日一题「643. 子数组最大平均数 I」非常像了,也和「424.
替换后的最长重复字符」非常像。这就是坚持刷每日一题的作用，继续坚持啊！

抽象之后，我们知道这是一个区间题，求子区间经常使用的方法就是滑动窗口。套模板即可

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.length();
        int left = 0, right = 0;//滑动窗口双指针
        int sum = 0, maxLen = INT_MIN;//sum存储窗口内的和
        //题中字符串关系转换成差值数组，问题转化为找差值数组满足maxCost的最长子串的和
        vector<int> dif(n);
        for(int i = 0; i < n; i++){
            dif[i] = abs(s[i] - t[i]);
        }
        //滑动窗口固定写法
        while(right < n){//循环边界条件
            sum += dif[right];//窗口内的计算
            while(sum > maxCost){//窗口移动的条件
                sum -= dif[left];
                left++;
            }
            maxLen = max(maxLen, right - left + 1);//题目要求解的
            right++;
        }
        return maxLen;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

leetcode1423. 可获得的最大点数

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

法1. 前缀和

当数据规模到达了 10 ^ 5 ，已经在提醒我们这个题应该使用 O(N) 的解法。

把今天的这个问题思路整理一下，题目等价于：

  求从 cardPoints 最左边抽 i 个数字，从 cardPoints 最右边抽取 k - i 个数字，能抽取获得的最大点数是多少。
1

一旦这么想，立马柳暗花明：抽走的卡牌点数之和 = cardPoints 所有元素之和 - 剩余的中间部分元素之和。
现在问题是怎么快速求 剩余的中间部分元素之和？

没错，preSum！下面是 preSum 的介绍：

   **求区间的和可以用 preSum** 。 preSum 方法还能快速计算指定区间段 i ~ j
  的元素之和。它的计算方法是从左向右遍历数组，当遍历到数组的 i 位置时， 				
  preSum 表示 i 位置左边的元素之和。
1
2
3

假设数组长度为 N ，我们定义一个长度为 N+1 的 preSum 数组， preSum[i]表示该元素左边所有元素之和（不包含当前元素）。然后遍历一次数组，累加区间 [0, i) 范围内的元素，可以得到 preSum数组。

前缀和模板代码如下：

N = len(nums)
preSum = range(N + 1)
for i in range(N):
    preSum[i + 1] = preSum[i] + nums[i]
print(preSum)
1
2
3
4
5

利用 preSum 数组，可以在 O(1) 的时间内快速求出 nums 任意区间 [i, j] (两端都包含) 的各元素之和。

sum(i, j) = preSum[i + 1] - preSum[j]

综合以上的思路，我们的想法可以先求 preSum ，然后使用一个 0 ~ k 的遍历表示从左边拿走的元素数，然后根据窗口大小 windowSize = N - k ，利用 preSum 快速求窗口内元素之和。

class Solution(object):
    def maxScore(self, cardPoints, k):
        """
        :type cardPoints: List[int]
        :type k: int
        :rtype: int
        """
        N = len(cardPoints)
        preSum = [0] * (N + 1)
        for i in range(N):
            preSum[i + 1] = preSum[i] + cardPoints[i]
        res = float("inf")
        windowSize = N - k
        for i in range(k + 1):
            res = min(res, preSum[windowSize + i] - preSum[i])
        return preSum[N] - res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

法2.滑动窗口

记数组 cardPoints 的长度为 n，由于只能从开头和末尾拿 k 张卡牌，所以最后剩下的必然是连续的 n−k 张卡牌。

我们可以通过求出剩余卡牌点数之和的最小值，来求出拿走卡牌点数之和的最大值。

由于剩余卡牌是连续的，使用一个固定长度为 n−k 的滑动窗口对数组 cardPoints
进行遍历，求出滑动窗口最小值，然后用所有卡牌的点数之和减去该最小值，即得到了拿走卡牌点数之和的最大值。

class Solution {
public:
    //该题正向思考有难度，可逆向转化为滑动窗口问题，找到长为n-k的连续子区间的和最小，那么两端取的k个值即为最大
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        int minSum = INT_MAX, allSum = 0, tmpSum = 0, left = 0, right = 0;

        //求总和
        for(const auto &p : cardPoints){
            allSum += p;
        }

        if(n == k){
            return allSum;
        }else{
            while(right < n){
            tmpSum += cardPoints[right];
            if(right >= n - k){//窗口有n-k个数后开始右移
                tmpSum -= cardPoints[left];
                left++;
                }
            if(right - left + 1 == n - k){//更新窗口最小的和
                minSum = min(minSum, tmpSum);
                }
            right++;
            }
        }
        return allSum - minSum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

leetcode978. 最长湍流子数组

法1.滑动窗口/双指针法

思路

湍流数组：实际把每个数看成点，点与点直接用边连起来，就应该是上下波动的样子///\，容易想到判断条件：满足（前一个点-中间点）*(后一个点-中间点)>0 的三个点都符合要求。(也可以分成两个条件，按<和>的情况判断)

以下为代码思路：

1. 要注意，套滑动窗口模板时，先处理掉特殊情况：前后两个数相同（平的边 /_/__/）

2. 平的边去掉后，按照上面说的条件，找符合要求的点：

      2.1 找到一个，窗口右边界就右移一位判断下一个；
      2.2 要遇到不满足的点（边）了，直接把做窗口左边界移动到该边的起始点（或者说此时不满足要求的右边界前一个点），中间的点都不必再遍历判断了，因为长度总是小于刚刚找到那个长度 找完一段就更新一下目前符合要求的最大长度
   1
   2

3. 移动窗口的左边界，继续寻找下面新的点，勿忘统计当前窗口内点个数的cnt重新置1（因为重新找下一段了）
   最后全数组遍历完即为满足要求的最长湍流子数组长度~

自己的代码

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        if(n == 1) return 1;
        int cnt = 1, left = 0, right = 1, maxLen = INT_MIN;//cnt记录滑动窗口当前的长度
        //滑动窗口:先过滤掉平的边，然后左边界固定，找到一个符合条件的右边界就右移一位；不满足时，左边界直接移动到不满足那条边的起始点，中间的点都可略过
        while(right < n){
            while(right < n && right - left == 1){//过滤掉平的边
                if(arr[right] - arr[left] != 0){//起始的(有起伏的)两个点总是要记录的
                    cnt++;
                    right++;
                }else{
                    left++;
                    right++;
                }
            }                 
            //两边点 减去 中间点 的差值 乘积为正，必然满足湍流子数组的条件
            while(right < n && (long)(arr[left+cnt-2] - arr[left+cnt-1]) * (arr[right] - arr[right-1]) > 0){
                cnt++;
                right++;//满足右边界移动接着往后找
            }
            maxLen = max(maxLen, cnt);//更新当前滑动窗口找到的符合要求的长度
            left = right - 1;//直接从不满足的地方开始找，把左边界移动到不满足的那条边的起始点
            cnt = 1;
        }
        return maxLen;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

官方给的代码

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        int ret = 1;
        int left = 0, right = 0;

        while (right < n - 1) {//注意此边界
            if (left == right) {
                if (arr[left] == arr[left + 1]) {
                    left++;
                }
                right++;
            } else {
                if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
                    right++;
                } else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
                    right++;
                } else {
                    left = right;
                }
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

法2.动态规划

思路

动态规划首先需要我们定义状态是什么，然后根据题意，写出状态转移方程。

对于最长连续子数组问题，使用动态规划求解时，我们经常定义状态 dp[i] 为：以 i 位置结尾的最长连续子数组的长度，因为这个状态可以反映 i 位置及其前面区间的情况。下一个位置 i + 1 可以根据 dp[i] 就知道了前面的情况，再根据 arr[i + 1] 和 arr[i]
的大小关系，能更新状态 dp[i + 1]。

对于本题，如果只定一个状态数组是不够的，因为我们只有区分了 i 位置是在增长还是在降低，才能判断 i + 1
位置是否能续上前面的波浪。所以，我们需要定义两个状态数组，分别表示以 i 结尾的在增长和降低的最长湍流子数组长度。

状态的定义：

  1. 定义 up[i] 表示以位置 i 结尾的，并且 arr[i - 1] < arr[i] 的最长湍流子数组长度。 
  2. 定义down[i] 表示以位置 i 结尾的，并且 arr[i - 1] > arr[i] 的最长湍流子数组长度。 
  up[i] 和 down[i]初始化都是 1，因为每个数字本身都是一个最小的湍流子数组。
1
2
3

状态转移方程：

  up[i] = down[i - 1] + 1，当 arr[i - 1] < arr[i]； down[i] = up[i - 1] + 1，当 arr[i - 1] > arr[i]；
   解释：湍流子数组的增长和降低是交替的。
1
2

文字的解释会显得苍白和啰嗦，大家直接看图吧。

对应python代码如下

class Solution(object):
    def maxTurbulenceSize(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        N = len(arr)
        up = [1] * N
        down = [1] * N
        res = 1
        for i in range(1, N):
            if arr[i - 1] < arr[i]:
                up[i] = down[i - 1] + 1
            elif arr[i - 1] > arr[i]:
                down[i] = up[i - 1] + 1
            res = max(res, max(up[i], down[i]))
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

c++代码

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(2, 1));//dp[i][0]代表当前i是下降，dp[i][1]代表当前i是上升
        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                dp[i][0] = dp[i - 1][1] + 1;
            } else if (arr[i - 1] < arr[i]) {
                dp[i][1] = dp[i - 1][0] + 1;
            }
        }

        int ret = 1;
        for (int i = 0; i < n; i++) {
            ret = max(ret, dp[i][0]);
            ret = max(ret, dp[i][1]);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

上述实现的空间复杂度是 O(n)。注意到当 i>0 时，下标 i 处的dp 值只和下标i−1 处的 dp 值有关，因此可以用两个变量 dp0 和 dp1 代替 dp[i][0] 和 dp[i][1]，将空间复杂度降到 O(1)。

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int ret = 1;
        int n = arr.size();
        int dp0 = 1, dp1 = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                dp0 = dp1 + 1;
                dp1 = 1;
            } else if (arr[i - 1] < arr[i]) {
                dp1 = dp0 + 1;
                dp0 = 1;
            } else {
                dp0 = 1;
                dp1 = 1;
            }
            ret = max(ret, dp0);
            ret = max(ret, dp1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

leetcode992. K 个不同整数的子数组

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。

思路

回想一下我们这几天已经做过的每日一题，都是求 「最长」「和/均值最大」的子数组，而今天这个题要我们求恰好有 K
个不同的整数组成的子数组。为了方便理解，我们还是需要从最值开始说起。

1. 最长子数组长度 我们先求一个简单问题：求 A 中由 K 个不同整数组成的最长子数组的长度。

def atMostK(self, A, K):
    N = len(A)
    left, right = 0, 0
    counter = collections.Counter()
    distinct = 0
    res = 0
    while right < N:
        if counter[A[right]] == 0:
            distinct += 1
        counter[A[right]] += 1
        while distinct > K:
            counter[A[left]] -= 1
            if counter[A[left]] == 0:
                distinct -= 1
            left += 1
        res = max(res, right - left + 1)
        right += 1
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这段代码的思想是：使用一个字典 counter，保存区间内每个数字出现的次数，使用一个变量 distinct
表示该区间中不同的数字个数（distinct 等于 counter 的 key 的数量）。下面讲一下两个 if。

• if counter[A[right]] == 0: distinct += 1 ，这是说，right 指向的位置不在counter中，是个新数字，所以 distinct += 1；
• if counter[A[left]] == 0: distinct -= 1，这是说，left 指针向右移动前，要把其原来指向的数字个数 - 1，当该数字的个数减到 0 了，则[left, right]区间内的不同数字的个数减少了一个，所以 distinct -= 1

其余代码和模板类似。

举例而言：对于 A = [1,2,1,2,3], K = 2，我们运行上面的代码会寻找到最长子数组 [1, 2, 1, 2] 的长度为 4.

2. 子数组个数 上面求的是 A 中由 K 个不同整数组成的最长子数组的长度，如果问 A 中由最多 K 个不同整数组成的子数组的个数，该怎么办呢？

答：只用把 res = max(res, right - left + 1) 改成 res += right - left + 1。

我们要求由最多 K 个不同整数组成的子数组的个数，那么对于长度 [left, right] 区间内的每个子数组都是满足要求的，res要累加的其实是 符合条件的 并且这个数量就是right - left + 1，即区间长度。原因如下：

用具体的例子理解：最多包含 3 种不同整数的子区间 [1, 3, 2, 3] （双指针算法是在左边界固定的前提下，让右边界走到最右边），当前可以确定 1 开始的满足最多包含 3 种不同整数的子区间有 [1]、[1, 3]、[1, 3, 2]、[1, 3, 2, 3]。
所有的 左边界固定前提下，根据右边界最右的下标，计算出来的子区间的个数就是整个函数要返回的值（用右边界固定的前提下，左边界最左边的下标去计算也是完全可以的），然后左边界移动在此计算新的个数，依次累加即为最多K个整数的子数组个数。

3. K 个不同整数的子数组的个数 看到这里，本题就差最后一哆嗦了。先给出结论：

恰好由 K 个不同整数的子数组的个数 = 最多由 K 个不同整数的子数组的个数 - 最多由 K - 1 个不同整数的子数组的个数

解释如下。

先来个通俗的：张三、李四、老王， 3 个人一起吃包子，他们最多能吃 10
个包子；如果有一天老王有事没来，现在只有张三、李四两个人吃包子，他们俩最多能吃 3 个包子。求老王的饭量是能吃几个包子？

可以用下面的图来帮助理解。

class Solution {
public:
    //统计最多有K个不同整数的子数组个数
    int atMostK(vector<int>& A, int K){
        int n = A.size();
        int right = 0, left = 0;
        unordered_map<int, int> count;//统计每个整数出现次数
        int distinct = 0, res = 0;//distinct是当前窗口内不同整数的个数，res统计子数组个数

        while(right < n){
            if(count[A[right]] == 0){//头一次出现
                distinct += 1;
            }
            count[A[right]]++;
            while(distinct > K){//超出K个右移左边界
                count[A[left]]--;
                if(count[A[left]] == 0) distinct--;
                left++;
            }
             // [left, right] 区间的长度就是对结果的贡献
            res += right - left + 1;//res = max(res, right - left + 1)是求解有K个不同整数的子数组最长长度
            right++;
        }
        return res;
    }

    //恰好有K个不同整数的子数组个数 = 最多有K个不同整数的子数组个数 - 最多K-1个。。。
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return atMostK(A, K) - atMostK(A, K - 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

该题讲解参考自：https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/cong-zui-jian-dan-de-wen-ti-yi-bu-bu-tuo-7f4v/

leetcode1004. 最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。

思路

该题类似上面第一道lc424

• 重点：题意转换。把「最多可以把 K 个 0 变成 1，求仅包含 1 的最长子数组的长度」转换为「找出一个最长的子数组，该子数组内最多允许有 K 个 0 」。

  1. 使用 left 和 right 两个指针，分别指向滑动窗口的左右边界。
  2. right 主动右移：right 指针每次移动一步。当 A[right] 为 0，说明滑动窗口内增加了一个 0；
  3. left 被动右移：判断此时窗口内 0 的个数，如果超过了 K，则 left 指针被迫右移，直至窗口内的 0 的个数小于等于 K 为止。
  4. 滑动窗口长度的最大值就是所求。

注意统计一下0的个数，和如何根据0的个数更新左指针即可~

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size();
        int left = 0, right = 0, zeroes = 0, ans = INT_MIN;

        while(right < n){
            if(A[right] == 0){//统计0的个数
                zeroes++;
            }
            while(zeroes > K){//移动左指针
                if(A[left] == 0){
                    zeroes--;
                }
                left++;
            }
            ans = max(ans, right - left + 1);//更新滑窗长度
            right++;//移动右指针
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

或用for循环也可以

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int res = 0, zeros = 0, left = 0;
        for (int right = 0; right < A.size(); ++right) {
            if (A[right] == 0) ++zeros;
            while (zeros > K) {
                if (A[left++] == 0) --zeros;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

后续滑动窗口例题详解 详见 第二篇