【25届秋招备战C++】算法篇

2024-07-12 01:52| 来源: 网络整理| 查看: 265

【25届秋招备战C++】算法篇-滑动窗口法一、简介二、解题步骤三、应用场景四、模板函数五、参考

一、简介

滑动窗口算法是一种在序列数据（如数组、字符串等）上执行特定操作的算法，它通过在序列上滑动一个固定大小的窗口来处理数据。这个窗口可以包含序列的一部分元素，并且随着算法的执行，窗口会沿着序列移动，主要用来减少while循环。滑动窗口算法的效率通常取决于窗口大小和序列长度。在最坏情况下，滑动窗口算法的时间复杂度为 O ( n ) \ O(n) O(n)，其中n是序列的长度。

二、解题步骤初始化：设置两个指针left和right，它们都指向序列的起始位置。初始化窗口大小（windowSize）和任何需要的辅助数据结构。填充窗口：根据需要对窗口内的元素进行操作，如计算和、计数等。滑动窗口：移动right指针向右，扩大窗口范围。如果窗口大小超过预设值，移动left指针向右，缩小窗口范围。更新操作：在每次窗口滑动后，根据需要更新窗口内的统计信息。重复步骤3和4：重复滑动窗口和更新操作，直到right指针到达序列的末尾。输出结果：输出最终的统计结果，如最大值、最小值、计数等。三、应用场景求最大/最小值：在给定的连续子数组/子序列中找到最大或最小值。计数问题：统计满足特定条件的连续子数组/子序列的数量。数据流问题：在数据流中维护特定统计信息，如移动平均值。子序列问题：检查是否存在满足特定条件的连续子序列。范围求和问题：计算给定范围内元素的和。四、模板函数 // 滑动窗口模板函数 template T slidingWindow(const std::vector& sequence, int windowSize, T identity) { T windowSum = identity; // 初始化窗口和，这里以整数为例，初始值为0 std::vector windowMax(windowSize, identity); // 用于存储窗口中的最大值 // 初始化窗口 for (int i = 0; i // 移除窗口最左边的元素，添加最右边的元素 windowSum -= sequence[i - windowSize]; windowSum += sequence[i]; // 更新窗口中的最大值 for (int j = 0; j windowMax[j] = sequence[i - windowSize + j]; } } // 更新最大窗口和 maxSum = std::max(maxSum, windowSum); // 根据具体问题更新结果 // 例如，如果我们要找到最大子数组和，这里可以不做任何操作 // 如果我们要找到最大子数组，可以在这里更新结果 } // 返回最终结果 return maxSum; }

在这里插入图片描述

五、参考

代码随想录滑动窗口算法技巧-爱学习的饲养员

【本文地址】

公司简介

联系我们