1. 从“窗口”到“滑动窗口”一道国赛题的算法内核解析最近在复盘蓝桥杯国赛真题时2022年Java B组的“窗口”这道题给我留下了挺深的印象。题目名字听起来平平无奇甚至有点让人摸不着头脑——是操作系统的窗口还是图形界面的窗口但当你真正读题并开始动手时就会发现这其实是一道非常经典的、考察滑动窗口算法思想的题目。它没有直接告诉你“请用滑动窗口解决”而是通过一个具体的、关于“窗口”内数值操作的场景来检验你是否能识别出问题背后的算法模型并熟练地实现它。这对于备赛的同学来说是一个极好的思维训练如何从模糊的描述中抽象出清晰的数学模型和算法逻辑。今天我就结合自己的解题经验把这个过程掰开揉碎了讲清楚不仅告诉你答案更重点分享“为什么这么想”以及“实现时有哪些坑”。2. 题目场景还原与核心需求拆解首先我们需要把题目中那个有些文学化的“窗口”描述翻译成程序员能理解的精确需求。根据我的回忆和常见题型这类“窗口”题通常设定如下假设我们有一个很长的数字序列比如一个数组arr长度可能达到10^5甚至更大。然后我们定义一个固定宽度的“窗口”这个窗口可以在这个序列上从左到右“滑动”。每次窗口覆盖序列的一个连续子区间。题目要求我们对于窗口在每一个可能的位置快速计算窗口内所有元素满足某个条件的值或者进行某种统计。最常见的操作包括求窗口内元素的最大值/最小值。求窗口内元素的和、平均值。判断窗口内是否存在某个特定元素或满足某种模式。对于2022年国赛这道题结合“蓝桥杯”一贯的考察风格偏向基础算法和数据结构的灵活应用以及“窗口”这个名称极大概率考察的是“滑动窗口最大值”或“滑动窗口和”的变体。可能是求每个窗口内某个特定统计值如最大值、最小值、和然后基于这些值进行下一步计算如求和、找极值等。2.1 为什么暴力法行不通一个最直观的想法是模拟窗口滑动过程。对于长度为n的序列和宽度为k的窗口总共有n-k1个窗口位置。对于每个窗口我们都遍历其中的k个元素进行计算。// 伪代码暴力法 O(n*k) for (int i 0; i n - k; i) { // i是窗口左端点 int windowSum 0; int windowMax Integer.MIN_VALUE; for (int j i; j i k; j) { // 遍历窗口内每个元素 windowSum arr[j]; windowMax Math.max(windowMax, arr[j]); } // 使用 windowSum 或 windowMax 进行后续操作 }这种方法的时间复杂度是 O(n * k)。在蓝桥杯的评测环境下n和k的数据范围通常会让这种解法超时。例如n10^5,k5*10^4那么操作次数将达到5*10^9量级远超1秒内能完成的运算量通常认为10^7~10^8是安全边界。因此我们必须寻找时间复杂度为 O(n)的优化方法这正是滑动窗口算法的用武之地。2.2 滑动窗口算法的核心思想利用相邻窗口的重叠部分滑动窗口算法高效的核心在于相邻的两个窗口有k-1个元素是重叠的。当我们从第i个窗口滑动到第i1个窗口时实际上只是移出了最左边的元素arr[i]。新加入了最右边的元素arr[ik]。如果我们能高效地维护一个数据结构使得在添加一个新元素和移除一个旧元素后能立刻得到当前窗口的统计信息如最大值、和那么整体复杂度就能降为 O(n)。对于“窗口和”问题这非常简单。我们维护一个当前窗口的和sum。当窗口右移时新sum 旧sum - arr[移出的下标] arr[新加入的下标]。 这样每个窗口的计算就是 O(1) 的。对于“窗口最大值”问题这就复杂了。移出一个元素后如果这个元素恰好是当前最大值我们无法快速知道剩余元素中谁最大除非重新遍历。这就需要借助更强大的数据结构。3. 利器单调队列解“滑动窗口最大值”“滑动窗口最大值”是滑动窗口系列中最经典也最需要技巧的问题。而解决它的标准利器就是单调队列。3.1 什么是单调队列单调队列是一种特殊的队列它保证了队列中的元素是单调的递增或递减。在解决“滑动窗口最大值”时我们维护一个单调递减队列。队头元素始终是当前窗口的最大值。它的“单调”特性是通过在入队时进行一系列“淘汰”操作来维持的。我们不仅关心元素的值还关心它的下标以判断它是否还在当前窗口内。3.2 算法步骤与Java实现详解我们来一步步拆解并用Java实现。假设数组为nums窗口大小为k。步骤一数据结构选择我们使用一个双端队列DequeInteger来存储元素的下标。存储下标是为了方便判断队头元素是否已经滑出窗口。ArrayDeque是一个高效的选择。步骤二处理前 k 个元素初始化第一个窗口遍历前k个元素维护单调递减队列。DequeInteger deque new ArrayDeque(); // 初始化第一个窗口 for (int i 0; i k; i) { // 关键操作1维护单调性。当新元素 队尾元素时弹出队尾 while (!deque.isEmpty() nums[i] nums[deque.peekLast()]) { deque.pollLast(); } // 将当前元素下标加入队尾 deque.offerLast(i); } // 此时队头下标对应的元素就是第一个窗口的最大值 int[] result new int[nums.length - k 1]; result[0] nums[deque.peekFirst()];为什么要在入队时弹出比新元素小的队尾因为那些较小的元素只要新元素还在窗口内它们就永远不可能成为最大值新元素比它们大且更晚过期。所以可以安全地从队列中剔除保证队列的递减性。步骤三滑动窗口计算后续每个窗口的最大值从第k个元素开始模拟窗口每次右移一位。for (int i k; i nums.length; i) { // 关键操作2移除滑出窗口的元素。检查队头下标是否小于窗口左边界 (i-k) if (!deque.isEmpty() deque.peekFirst() i - k) { deque.pollFirst(); } // 关键操作3同步骤二维护单调性将新元素下标 i 加入队列 while (!deque.isEmpty() nums[i] nums[deque.peekLast()]) { deque.pollLast(); } deque.offerLast(i); // 当前窗口右边界为i的最大值就是队头元素 result[i - k 1] nums[deque.peekFirst()]; }完整代码整合import java.util.ArrayDeque; import java.util.Deque; public class SlidingWindowMaximum { public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0 || k 0) { return new int[0]; } int n nums.length; int[] result new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 移除滑出窗口的元素 if (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 2. 维护单调递减队列 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 3. 存入当前下标 deque.offerLast(i); // 4. 当窗口形成时记录结果 if (i k - 1) { result[i - k 1] nums[deque.peekFirst()]; } } return result; } }注意边界条件的判断deque.peekFirst() i - k 1是关键。窗口的左边界是i - k 1如果队头下标小于这个值说明它已经不在窗口内了。3.3 时间复杂度与空间复杂度分析时间复杂度 O(n)数组中的每个元素恰好被加入队列一次并且最多被弹出队列一次。因此每个元素的操作是均摊 O(1)的总复杂度为 O(n)。空间复杂度 O(k)单调队列最多同时存储k个元素当输入数组完全递减时。4. 实战推演如何应对国赛题的可能变体国赛题不会直接考你一个裸的“滑动窗口最大值”一定会加上一些背景和变形。我们基于“窗口”这个主题来推测和演练几种可能的变体。4.1 变体一窗口内最大值之和这是最直接的变体。题目可能描述为有一个长度为n的数字序列一个宽度为m的窗口从左滑动到右记下每个窗口内的最大值。最后要求所有窗口最大值的总和。解法先用上述单调队列算法求出result数组存储每个窗口的最大值然后对result数组求和即可。复杂度依然是 O(n)。4.2 变体二基于窗口最大值的阈值统计题目可能描述为对于每个窗口如果其最大值大于某个阈值T则计数器加一。最后求计数器的值。或者需要将每个窗口的最大值与另一个序列对应位置的值进行比较、运算。解法核心仍然是先求出每个窗口的最大值数组。得到这个数组后再进行一遍线性扫描进行判断或计算。整个算法的瓶颈仍在求最大值数组这一步。4.3 变体三窗口内“第二大值”或“第K大值”这难度就上了一个台阶。单调队列只能维护最大值或最小值。求第K大值一种思路是使用两个单调队列这行不通。更通用的方法是使用平衡二叉搜索树如Java中的TreeMap来维护窗口内的元素。思路TreeMap的键是元素值值是该值在窗口中出现的次数。窗口滑动时移出左元素将其在 map 中的计数减1若减为0则移除该键。加入右元素将其在 map 中的计数加1或放入。查询第K大可以通过TreeMap的lastKey()获取最大但要获取第K大需要倒序遍历或使用lowerKey()等方法复杂度会上升到 O(log n * k) 或 O(n log n)不是严格的 O(n)。对于国赛可能不会考察这么复杂的在线第K大查询更可能是求最大值或最小值。4.4 变体四二维窗口或环形数组上的窗口二维窗口例如在一个矩阵上有一个a x b的矩形窗口滑动求每个位置矩形窗口内的最大值。这需要将一维的单调队列推广到二维通常先在每一行上做一次一维滑动窗口得到一个中间矩阵再在每一列上对中间矩阵做一次一维滑动窗口。复杂度为 O(行数 * 列数)。环形数组数组是首尾相连的。窗口滑动可以越过末尾到达开头。处理方法是将原数组复制一份拼接在末尾形成一个长度为2n的数组然后在这个数组上做长度为k的滑动窗口注意窗口总数可能变多最后只取有效部分的结果。需要仔细处理下标取模。5. 备赛训练与调试技巧知道算法原理只是第一步在比赛高压环境下稳定写出 bug-free 的代码才是关键。5.1 常见错误点排查清单队列中存值还是存下标必须存下标否则无法判断队头元素是否已滑出窗口。窗口边界计算错误这是最易出错的地方。窗口左边界是i - k 1不是i - k。在初始化结果数组时其长度是n - k 1。务必用一个小例子如 n5, k3手动模拟验证下标。单调性的维护条件求最大值时是nums[i] nums[deque.peekLast()]时弹出队尾保证了相等的新元素会淘汰旧的因为新的更晚过期。求最小值时则使用。空队列判断在peekFirst()或pollFirst()前养成习惯先判断!deque.isEmpty()。输入特判如果k n怎么办如果k 0怎么办如果数组为空怎么办好的代码应该在一开始就处理这些边界情况。5.2 调试与对数器方法在平时练习时不要只相信样例。暴力法作为对数器写一个 O(n*k) 的暴力解法虽然慢但对于小数据量n 1000绝对是正确的。用它来验证你的单调队列算法。随机数据生成用随机数生成器产生数组和窗口大小分别用暴力法和你的优化算法跑比较结果是否一致。打印中间状态在本地调试时可以在循环中打印出每一步的队列内容、当前窗口边界和结果非常有助于理解算法流程和发现下标错误。// 简单的随机测试框架 import java.util.Random; public class Test { public static void main(String[] args) { Random rand new Random(); int testTime 10000; for (int t 0; t testTime; t) { int n rand.nextInt(100) 1; // 数组长度 1~100 int k rand.nextInt(n) 1; // 窗口大小 1~n int[] arr new int[n]; for (int i 0; i n; i) { arr[i] rand.nextInt(1000) - 500; // 生成负数、正数 } int[] res1 bruteForce(arr, k); int[] res2 maxSlidingWindow(arr, k); // 比较 res1 和 res2 每个位置是否相等 if (!Arrays.equals(res1, res2)) { System.out.println(出错); System.out.println(arr: Arrays.toString(arr)); System.out.println(k: k); System.out.println(暴力结果: Arrays.toString(res1)); System.out.println(单调队列结果: Arrays.toString(res2)); break; } } System.out.println(测试通过); } // 实现 bruteForce 和 maxSlidingWindow 方法... }5.3 赛场策略快速识别看到“窗口”、“滑动”、“连续子数组”、“最大值/最小值”等关键词立刻联想到滑动窗口和单调队列。先写暴力保分如果一时想不出优化解法先写一个暴力解法提交确保拿到基础分。蓝桥杯是OI赛制有部分分。默写模板单调队列解决滑动窗口最大/最小值是一个高度模板化的算法。平时就要练到肌肉记忆比赛时才能快速无误地写出来。小心审题国赛题往往有“坑”。仔细阅读数据范围、输出格式。窗口最大值是要求输出所有值还是它们的和、乘积、亦或是再进行某种映射
滑动窗口算法与单调队列：从原理到蓝桥杯国赛实战解析
1. 从“窗口”到“滑动窗口”一道国赛题的算法内核解析最近在复盘蓝桥杯国赛真题时2022年Java B组的“窗口”这道题给我留下了挺深的印象。题目名字听起来平平无奇甚至有点让人摸不着头脑——是操作系统的窗口还是图形界面的窗口但当你真正读题并开始动手时就会发现这其实是一道非常经典的、考察滑动窗口算法思想的题目。它没有直接告诉你“请用滑动窗口解决”而是通过一个具体的、关于“窗口”内数值操作的场景来检验你是否能识别出问题背后的算法模型并熟练地实现它。这对于备赛的同学来说是一个极好的思维训练如何从模糊的描述中抽象出清晰的数学模型和算法逻辑。今天我就结合自己的解题经验把这个过程掰开揉碎了讲清楚不仅告诉你答案更重点分享“为什么这么想”以及“实现时有哪些坑”。2. 题目场景还原与核心需求拆解首先我们需要把题目中那个有些文学化的“窗口”描述翻译成程序员能理解的精确需求。根据我的回忆和常见题型这类“窗口”题通常设定如下假设我们有一个很长的数字序列比如一个数组arr长度可能达到10^5甚至更大。然后我们定义一个固定宽度的“窗口”这个窗口可以在这个序列上从左到右“滑动”。每次窗口覆盖序列的一个连续子区间。题目要求我们对于窗口在每一个可能的位置快速计算窗口内所有元素满足某个条件的值或者进行某种统计。最常见的操作包括求窗口内元素的最大值/最小值。求窗口内元素的和、平均值。判断窗口内是否存在某个特定元素或满足某种模式。对于2022年国赛这道题结合“蓝桥杯”一贯的考察风格偏向基础算法和数据结构的灵活应用以及“窗口”这个名称极大概率考察的是“滑动窗口最大值”或“滑动窗口和”的变体。可能是求每个窗口内某个特定统计值如最大值、最小值、和然后基于这些值进行下一步计算如求和、找极值等。2.1 为什么暴力法行不通一个最直观的想法是模拟窗口滑动过程。对于长度为n的序列和宽度为k的窗口总共有n-k1个窗口位置。对于每个窗口我们都遍历其中的k个元素进行计算。// 伪代码暴力法 O(n*k) for (int i 0; i n - k; i) { // i是窗口左端点 int windowSum 0; int windowMax Integer.MIN_VALUE; for (int j i; j i k; j) { // 遍历窗口内每个元素 windowSum arr[j]; windowMax Math.max(windowMax, arr[j]); } // 使用 windowSum 或 windowMax 进行后续操作 }这种方法的时间复杂度是 O(n * k)。在蓝桥杯的评测环境下n和k的数据范围通常会让这种解法超时。例如n10^5,k5*10^4那么操作次数将达到5*10^9量级远超1秒内能完成的运算量通常认为10^7~10^8是安全边界。因此我们必须寻找时间复杂度为 O(n)的优化方法这正是滑动窗口算法的用武之地。2.2 滑动窗口算法的核心思想利用相邻窗口的重叠部分滑动窗口算法高效的核心在于相邻的两个窗口有k-1个元素是重叠的。当我们从第i个窗口滑动到第i1个窗口时实际上只是移出了最左边的元素arr[i]。新加入了最右边的元素arr[ik]。如果我们能高效地维护一个数据结构使得在添加一个新元素和移除一个旧元素后能立刻得到当前窗口的统计信息如最大值、和那么整体复杂度就能降为 O(n)。对于“窗口和”问题这非常简单。我们维护一个当前窗口的和sum。当窗口右移时新sum 旧sum - arr[移出的下标] arr[新加入的下标]。 这样每个窗口的计算就是 O(1) 的。对于“窗口最大值”问题这就复杂了。移出一个元素后如果这个元素恰好是当前最大值我们无法快速知道剩余元素中谁最大除非重新遍历。这就需要借助更强大的数据结构。3. 利器单调队列解“滑动窗口最大值”“滑动窗口最大值”是滑动窗口系列中最经典也最需要技巧的问题。而解决它的标准利器就是单调队列。3.1 什么是单调队列单调队列是一种特殊的队列它保证了队列中的元素是单调的递增或递减。在解决“滑动窗口最大值”时我们维护一个单调递减队列。队头元素始终是当前窗口的最大值。它的“单调”特性是通过在入队时进行一系列“淘汰”操作来维持的。我们不仅关心元素的值还关心它的下标以判断它是否还在当前窗口内。3.2 算法步骤与Java实现详解我们来一步步拆解并用Java实现。假设数组为nums窗口大小为k。步骤一数据结构选择我们使用一个双端队列DequeInteger来存储元素的下标。存储下标是为了方便判断队头元素是否已经滑出窗口。ArrayDeque是一个高效的选择。步骤二处理前 k 个元素初始化第一个窗口遍历前k个元素维护单调递减队列。DequeInteger deque new ArrayDeque(); // 初始化第一个窗口 for (int i 0; i k; i) { // 关键操作1维护单调性。当新元素 队尾元素时弹出队尾 while (!deque.isEmpty() nums[i] nums[deque.peekLast()]) { deque.pollLast(); } // 将当前元素下标加入队尾 deque.offerLast(i); } // 此时队头下标对应的元素就是第一个窗口的最大值 int[] result new int[nums.length - k 1]; result[0] nums[deque.peekFirst()];为什么要在入队时弹出比新元素小的队尾因为那些较小的元素只要新元素还在窗口内它们就永远不可能成为最大值新元素比它们大且更晚过期。所以可以安全地从队列中剔除保证队列的递减性。步骤三滑动窗口计算后续每个窗口的最大值从第k个元素开始模拟窗口每次右移一位。for (int i k; i nums.length; i) { // 关键操作2移除滑出窗口的元素。检查队头下标是否小于窗口左边界 (i-k) if (!deque.isEmpty() deque.peekFirst() i - k) { deque.pollFirst(); } // 关键操作3同步骤二维护单调性将新元素下标 i 加入队列 while (!deque.isEmpty() nums[i] nums[deque.peekLast()]) { deque.pollLast(); } deque.offerLast(i); // 当前窗口右边界为i的最大值就是队头元素 result[i - k 1] nums[deque.peekFirst()]; }完整代码整合import java.util.ArrayDeque; import java.util.Deque; public class SlidingWindowMaximum { public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0 || k 0) { return new int[0]; } int n nums.length; int[] result new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 移除滑出窗口的元素 if (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 2. 维护单调递减队列 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 3. 存入当前下标 deque.offerLast(i); // 4. 当窗口形成时记录结果 if (i k - 1) { result[i - k 1] nums[deque.peekFirst()]; } } return result; } }注意边界条件的判断deque.peekFirst() i - k 1是关键。窗口的左边界是i - k 1如果队头下标小于这个值说明它已经不在窗口内了。3.3 时间复杂度与空间复杂度分析时间复杂度 O(n)数组中的每个元素恰好被加入队列一次并且最多被弹出队列一次。因此每个元素的操作是均摊 O(1)的总复杂度为 O(n)。空间复杂度 O(k)单调队列最多同时存储k个元素当输入数组完全递减时。4. 实战推演如何应对国赛题的可能变体国赛题不会直接考你一个裸的“滑动窗口最大值”一定会加上一些背景和变形。我们基于“窗口”这个主题来推测和演练几种可能的变体。4.1 变体一窗口内最大值之和这是最直接的变体。题目可能描述为有一个长度为n的数字序列一个宽度为m的窗口从左滑动到右记下每个窗口内的最大值。最后要求所有窗口最大值的总和。解法先用上述单调队列算法求出result数组存储每个窗口的最大值然后对result数组求和即可。复杂度依然是 O(n)。4.2 变体二基于窗口最大值的阈值统计题目可能描述为对于每个窗口如果其最大值大于某个阈值T则计数器加一。最后求计数器的值。或者需要将每个窗口的最大值与另一个序列对应位置的值进行比较、运算。解法核心仍然是先求出每个窗口的最大值数组。得到这个数组后再进行一遍线性扫描进行判断或计算。整个算法的瓶颈仍在求最大值数组这一步。4.3 变体三窗口内“第二大值”或“第K大值”这难度就上了一个台阶。单调队列只能维护最大值或最小值。求第K大值一种思路是使用两个单调队列这行不通。更通用的方法是使用平衡二叉搜索树如Java中的TreeMap来维护窗口内的元素。思路TreeMap的键是元素值值是该值在窗口中出现的次数。窗口滑动时移出左元素将其在 map 中的计数减1若减为0则移除该键。加入右元素将其在 map 中的计数加1或放入。查询第K大可以通过TreeMap的lastKey()获取最大但要获取第K大需要倒序遍历或使用lowerKey()等方法复杂度会上升到 O(log n * k) 或 O(n log n)不是严格的 O(n)。对于国赛可能不会考察这么复杂的在线第K大查询更可能是求最大值或最小值。4.4 变体四二维窗口或环形数组上的窗口二维窗口例如在一个矩阵上有一个a x b的矩形窗口滑动求每个位置矩形窗口内的最大值。这需要将一维的单调队列推广到二维通常先在每一行上做一次一维滑动窗口得到一个中间矩阵再在每一列上对中间矩阵做一次一维滑动窗口。复杂度为 O(行数 * 列数)。环形数组数组是首尾相连的。窗口滑动可以越过末尾到达开头。处理方法是将原数组复制一份拼接在末尾形成一个长度为2n的数组然后在这个数组上做长度为k的滑动窗口注意窗口总数可能变多最后只取有效部分的结果。需要仔细处理下标取模。5. 备赛训练与调试技巧知道算法原理只是第一步在比赛高压环境下稳定写出 bug-free 的代码才是关键。5.1 常见错误点排查清单队列中存值还是存下标必须存下标否则无法判断队头元素是否已滑出窗口。窗口边界计算错误这是最易出错的地方。窗口左边界是i - k 1不是i - k。在初始化结果数组时其长度是n - k 1。务必用一个小例子如 n5, k3手动模拟验证下标。单调性的维护条件求最大值时是nums[i] nums[deque.peekLast()]时弹出队尾保证了相等的新元素会淘汰旧的因为新的更晚过期。求最小值时则使用。空队列判断在peekFirst()或pollFirst()前养成习惯先判断!deque.isEmpty()。输入特判如果k n怎么办如果k 0怎么办如果数组为空怎么办好的代码应该在一开始就处理这些边界情况。5.2 调试与对数器方法在平时练习时不要只相信样例。暴力法作为对数器写一个 O(n*k) 的暴力解法虽然慢但对于小数据量n 1000绝对是正确的。用它来验证你的单调队列算法。随机数据生成用随机数生成器产生数组和窗口大小分别用暴力法和你的优化算法跑比较结果是否一致。打印中间状态在本地调试时可以在循环中打印出每一步的队列内容、当前窗口边界和结果非常有助于理解算法流程和发现下标错误。// 简单的随机测试框架 import java.util.Random; public class Test { public static void main(String[] args) { Random rand new Random(); int testTime 10000; for (int t 0; t testTime; t) { int n rand.nextInt(100) 1; // 数组长度 1~100 int k rand.nextInt(n) 1; // 窗口大小 1~n int[] arr new int[n]; for (int i 0; i n; i) { arr[i] rand.nextInt(1000) - 500; // 生成负数、正数 } int[] res1 bruteForce(arr, k); int[] res2 maxSlidingWindow(arr, k); // 比较 res1 和 res2 每个位置是否相等 if (!Arrays.equals(res1, res2)) { System.out.println(出错); System.out.println(arr: Arrays.toString(arr)); System.out.println(k: k); System.out.println(暴力结果: Arrays.toString(res1)); System.out.println(单调队列结果: Arrays.toString(res2)); break; } } System.out.println(测试通过); } // 实现 bruteForce 和 maxSlidingWindow 方法... }5.3 赛场策略快速识别看到“窗口”、“滑动”、“连续子数组”、“最大值/最小值”等关键词立刻联想到滑动窗口和单调队列。先写暴力保分如果一时想不出优化解法先写一个暴力解法提交确保拿到基础分。蓝桥杯是OI赛制有部分分。默写模板单调队列解决滑动窗口最大/最小值是一个高度模板化的算法。平时就要练到肌肉记忆比赛时才能快速无误地写出来。小心审题国赛题往往有“坑”。仔细阅读数据范围、输出格式。窗口最大值是要求输出所有值还是它们的和、乘积、亦或是再进行某种映射
