滑动窗口算法：高效处理数组与字符串子序列问题的利器

滑动窗口算法是一种用于处理数组或字符串子序列问题的高效技术。其核心思想是通过维护一个固定大小的窗口（或多个元素的子集），在数据结构上滑动该窗口，从而在每一步中计算或检查窗口内的元素，以满足特定的条件或目标。

滑动窗口算法的基本原理

窗口的定义

● 固定大小窗口：窗口的大小在算法执行过程中保持不变。
● 可变大小窗口：窗口的大小可以根据需要动态调整，通常用于寻找满足特定条件的子数组或子字符串。

滑动过程

● 扩展窗口：通过移动窗口的右边界（通常称为right指针）来包含新的元素。
● 收缩窗口：当窗口内满足某些条件时，通过移动窗口的左边界（通常称为left指针）来排除不再需要的元素，以寻找更优的解或满足特定约束。

维护窗口内的信息

● 使用适当的数据结构（如哈希表、双端队列等）来跟踪窗口内元素的信息，以便快速计算或验证条件。
滑动窗口的应用场景
● 最大/最小子数组问题：例如，找到数组中连续k个元素的最大和。
● 最长/最短子串问题：例如，找到包含所有目标字符的最短子串。
● 字符串匹配：例如，判断一个字符串是否包含另一个字符串的所有排列。
● 存在性问题：例如，判断是否存在一个子数组，其元素之和等于目标值。

滑动窗口的可用条件（单调性）

如果(left, right)满足状态（题目要求），则(left, right+1 ... end) 也满足状态。遍历时右移 left 指针。
如果(left, right)不满足状态（题目要求），则(left+1... right, end) 也不满足状态。遍历时右移 right 指针。

滑动窗口的实现步骤

初始化：
○ 设置两个指针，通常称为left和right，表示窗口的左右边界。
○ 初始化一个数据结构来存储窗口内的元素信息。
扩展窗口：
○ 移动right指针，将新元素纳入窗口。
○ 更新窗口内的信息（如总和、计数等）。
检查条件：
○ 当窗口大小满足要求或窗口内元素满足特定条件时，记录结果或进行相应处理。
收缩窗口：
○ 移动left指针，移出窗口左边的元素。
○ 更新窗口内的信息。
重复步骤2-4，直到right指针到达数组或字符串的末尾。

滑动窗口算法的优化

● 使用双端队列（Deque）：
○ 适用于需要维护窗口内最大值或最小值的场景。
○ 通过保持队列的单调性，可以在O(1)时间内获取窗口内的极值。
● 哈希表：
○ 用于记录窗口内元素的出现次数，适用于需要统计元素频率的问题。
● 前缀和：
○ 通过预先计算数组的前缀和，可以快速计算任意子数组的和，从而优化滑动窗口内的求和操作。

示例

LeetCode 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ant = 0;
        unordered_map<int, int> mp;
        for (int left = 0, right = 0; right < s.length(); right++) {
            mp[s[right]]++;
            while(mp[s[right]] > 1) {
                mp[s[left]]--;
                left++;
            }
            ant = max(ant, right - left + 1);
        }
        return ant;
    }
};

统计好子数组的数目

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long count = 0;
        long long ant = 0;
        unordered_map<int, int> mp;
        for(int left =0, right = 0; right < nums.size(); right++) {
            ant += mp[nums[right]]++;
            while (ant >= k) {               
                ant -= --mp[nums[left]];
                left++;
            }
            count += left;
        }
        return count;
    }
};

示例：滑动窗口最大值

#include <iostream>
#include <vector>
#include <deque>  

using namespace std;  

vector<int> maxSlidingWindow(vector<int>& nums, int k) {     
    vector<int> result;     
    deque<int> dq; // 双端队列，存储窗口内潜在的最大值的索引     

    for(int i = 0; i < nums.size(); ++i){         
        // 移除队列中不在当前窗口范围内的索引         
        while(!dq.empty() && dq.front() < i - k + 1){             
            dq.pop_front();         
        }         
        // 移除队列中所有小于当前元素的索引，保证队列头部始终是最大值的索引         
        while(!dq.empty() && nums[dq.back()] < nums[i]){             
            dq.pop_back();         
        }         
        // 将当前元素的索引加入队列         
        dq.push_back(i);         
        // 当窗口大小达到k时，记录队列头部的最大值         
        if(i >= k - 1){             
            result.push_back(nums[dq.front()]);         
        }     
    }     
  
    return result; 
}  

int main(){
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for(auto num : res){
        cout << num << " ";
    }
    return 0;
}

输出：

3 3 5 5 6 7

解释：
● 使用双端队列dq来维护当前窗口内的最大值的索引。
● 队列始终保持单调递减，队首始终是当前窗口的最大值。
● 每当窗口滑动时，更新队列并记录最大值。
总结
滑动窗口算法通过动态调整窗口的位置和大小，能够在O(n)的时间复杂度内解决一系列子数组或子字符串的问题，极大地提高了效率。理解和掌握滑动窗口的原理及其优化方法，对于解决复杂的数据处理问题具有重要意义。