题⽬描述

给定⼀个数组和滑动窗⼝的⼤⼩，找出所有滑动窗⼝⾥数值的最⼤值。例如，如果输⼊数组 {2,3,4,2,6,2,5,1} 及滑动窗⼝的⼤⼩ 3，那么⼀共存在 6 个滑动窗⼝，他们的最⼤值分别为 {4,4,6,6,6,5} ；

针对数组 {2,3,4,2,6,2,5,1} 的滑动窗⼝有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4, [2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]} 。 窗⼝⼤于数组⻓度的时候，返回空。

思路及解答

暴力法

遍历每个可能的窗口起始位置，计算窗口内的最大值

  • 时间复杂度：O(n×k)，需要处理n-k+1个窗口，每个窗口需要k次比较

  • 空间复杂度：O(1)，除结果数组外只使用常数空间

双端队列法（最优解）

⾸先进⾏⾮空判断，以及数组⻓度是否不为 0，是否不⼩于窗⼝⻓度。

其次，使⽤⼀个双向链表，⾥⾯保存的是索引，遍历每⼀个元素，如果双向队列不为空且最后的元素作为索引的数值⼩于当前的元素，就把当前的元素的索引加到队列的后⾯。（这样可以保证队列从头到尾是单调递减的，也就是队尾的元素就是最⼩的元素）。

然后把当前的元素加进去队列尾部。判断队列前⾯的元素是不是索引位置不符合，如果不符合，就移除队列头部的元素。

那么此时的队列⾸部肯定就是滑动窗⼝的最⼤值。（此处应该判断滑动窗⼝⽣效的索引）

  • 时间复杂度：O（n）,所有的元素都进⼊队列，再出队列

  • 空间复杂度：O(n)，使⽤额外的队列空间存储索引以及窗⼝最⼤值。

动态规划法（分块思想）

将数组分成大小为k的块，预处理每个位置的左右最大值。核心思想就是 空间换时间，提前把部分结果算好存起来，让后续的查询变成 O(1) 的查表操作。

对于任何一个长度为 k 的滑动窗口，它最多只会横跨 两个 相邻的块。既然只跨两块，我们只要提前知道每块内部各个位置的“局部最大值”，就能瞬间拼出整个窗口的最大值！

分块思想：

  • 将数组划分为大小为k的块（最后一块可能不满）

  • left[i]：从当前块开始到位置i的最大值

  • right[i]：从位置i到当前块结束的最大值

窗口最大值计算：

对于窗口[i, i+k-1]：

  • 如果窗口完全在一个块内：right[i]或left[i+k-1]就是最大值

  • 如果窗口跨越两个块：最大值 = max(右块的左最大值, 左块的右最大值) = max( right[i], left[i+k-1] )

为什么这个公式永远成立？

  • 情况 A（窗口跨越两个块）：窗口被切成了两半。right[i] 完美涵盖了窗口在左半边块里的最大值；left[i+k-1] 完美涵盖了窗口在右半边块里的最大值。两者取最大，就是整个窗口的最大值！

  • 情况 B（窗口刚好是一个完整的块）：此时 right[i] 和 left[i+k-1] 都等于这整个块的最大值，取最大依然是正确答案。

以题目中的 {2,3,4,2,6,2,5,1}，窗口大小 k=3 为例：

  1. 构建 left (前缀最大值)：

  • 块1 [2,3,4] -> left: [2, 3, 4]

  • 块2 [2,6,2] -> left: [2, 6, 6]

  • 块3 [5,1] -> left: [5, 5]

  1. 构建 right (后缀最大值)：

  • 块1 [2,3,4] -> right: [4, 4, 4]

  • 块2 [2,6,2] -> right: [6, 6, 2]

  • 块3 [5,1] -> right: [5, 1]

  1. 计算窗口结果：

  • 第1个窗口 [2,3,4]：max(right[0], left[2]) = max(4, 4) = 4

  • 第2个窗口 [3,4,2] (跨越块1和块2)：max(right[1], left[3]) = max(4, 2) = 4

  • 第3个窗口 [4,2,6] (跨越块1和块2)：max(right[2], left[4]) = max(4, 6) = 6

  • …以此类推，所有结果都能瞬间得出！

算法分析：

  • 时间复杂度：O(n)，三次线性遍历

  • 空间复杂度：O(n)，需要两个辅助数组