一、定义与基本原理
滑动窗口是一种流量控制技术，也用于管理和处理数据流。它通过定义一个固定大小或可根据特定条件动态调整的窗口，在数据流或数据序列上滑动，以便高效地处理其中的数据。这种技术能够限制同时处理的数据量，从而控制资源消耗并提高处理效率。
二、类型与特点
- 固定窗口：窗口大小固定不变，通常用于数据流的分段处理。
- 动态窗口：窗口大小可以根据特定条件动态调整，用于适应变化的网络或数据流特性。
滑动窗口的核心思想是通过一个窗口在数据流或数据序列上滑动，逐步覆盖整个数据流或数据序列，同时根据窗口内的数据满足特定条件时进行相应处理。
三、应用领域
-
网络通信：
- 在TCP协议中，滑动窗口机制用于传输控制，通过接收方返回的确认信息来控制数据的发送速率，优化网络吞吐量和防止数据丢失。
- 滑动窗口不仅是一个顺序控制的工具，更是一个流量控制和拥塞控制的重要手段。
-
算法设计：
- 滑动窗口法经常用于解决涉及到子字符串或子数组的问题，例如寻找给定长度的最大/最小值，或满足特定条件的子序列。
- 它可以用于求解最长无重复子串、最小覆盖子串、长度为k的最小子数组等经典问题。
- 滑动窗口算法：通常会设置俩个指针，一个指向窗口的左边界，另一个指向窗口的右边界。开始时，窗口的大小为0，然后右指针向右移动，直到满足特定条件为止。一旦满足条件，窗口的大小就会增加，然后左指针向右移动，直到不再满足条件为止。这样，窗口会不断滑动，直到遍历完整个数组或字符串，从而找到满足条件的子数组或子字符串。
-
图像处理：
- 在图像处理领域，滑动窗口技术可以用于图像分割、特征提取等任务。
-
数据流处理：
- 在数据流处理系统中，滑动窗口技术用于对连续的数据流进行分段处理和分析。
四、工作机制与示例
以TCP协议中的滑动窗口为例，其工作机制如下：
- 接收方告诉发送方在某一时刻能送多少包（称窗口尺寸）。
- TCP中采用滑动窗口来进行传输控制，滑动窗口的大小意味着接收方还有多大的缓冲区可以用于接收数据。
- 发送方可以通过滑动窗口的大小来确定应该发送多少字节的数据。
- 当滑动窗口为0时，发送方一般不能再发送数据包，但有两种情况除外：一是可以发送紧急数据，例如允许用户终止在远端机上的运行进程；二是发送方可以发送一个1字节的数据报来通知接收方重新声明它希望接收的下一字节及发送方的滑动窗口大小。
五、优势与挑战
-
优势：
- 滑动窗口技术能够显著提高系统的效率和响应能力。
- 它通过限制在任何给定时间可以发送或接收的数据包的数量，允许使用固定大小的序列号传送无限数量的数据包。
-
挑战：
- 选择合适的窗口大小是一个挑战，窗口过大可能导致资源消耗过多，窗口过小则可能影响处理效率。
- 在处理边界数据时也需要特别注意，以避免出现错误或遗漏。
综上所述，滑动窗口是一种高效且灵活的数据管理和处理技术，在多个领域都有广泛的应用。通过合理设计和优化，滑动窗口可以广泛应用于各种数据密集型任务中。
算法题
1.求长度最小的子数组
int MinSubArrayLen(int target, std::vector<int>& nums)
{int len = INT32_MAX;int n = nums.size(), sum = 0;int left = 0, right = 0;for (; right < n; right++){sum += nums[right];while (sum >= target){if (sum == target) //如果想找等于的就加上这行len = len < right - left + 1 ? len : right - left + 1;sum -= nums[left++];}}return len == INT32_MAX ? 0 : len;
}int MaxSubArrayLen(int target, std::vector<int>& nums)
{int len = INT32_MIN;int n = nums.size(), sum = 0;int left = 0, right = 0;for (; right < n; right++){sum += nums[right];while (sum >= target){if (sum == target) //如果想找等于的就加上这行len = len > right - left + 1 ? len : right - left + 1;sum -= nums[left++];}}return len == INT32_MIN ? 0 : len;
}int main()
{std::vector<int> a = { 2,3,5,3,5,2,4,1,9,5,5 };int lenMin = MinSubArrayLen(17, a); //输出为0int lenMax = MaxSubArrayLen(15, a); //输出为5std::cout << lenMin << std::endl;std::cout << lenMax << std::endl;return 0;
}2.无重复最长字串
采取哈希表统计字符个数，滑动窗口控制子串长度的操作，当right处于一个新位置就将其加入窗口，若当前字符的出现次数 > 1则表明当前字符串出现重复字符，此时让left所在位置的元素出窗口，直到当前字符出现次数 == 1
int MaxStringLen(std::string& src)
{int len = INT32_MIN, n = src.size();std::unordered_map<char, int> hash;int left = 0, right = 0;for (; right < n; right++){char in = src[right];hash[in]++;while (hash[in] > 1){char out = src[left++];hash[out]--;}len = len > right - left + 1 ? len : right - left + 1;}return len;
}int main()
{std::string s = "acbcag";int len = MaxStringLen(s);std::cout << len << std::endl;return 0;
}
