题目描述

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

###解题思路(线性解法)
以上图举例,需要在遍历数组的同时,将最大值找出。由于希望是线性查找到最大值,因此我们需要维持一个数据结构,该数据结构的特性可以使用O(1)的时间找到最大值,因此我们可以使用双端队列,该队列可以动态改变头与尾的随数据,我们只需要将最大值一直维护在该队列的头。

双端队列

由于没有特殊要求,只需要不断的更新队列,在Go语言中可以使用切片快速实现这一数据结构的特性。

代码思路

  1. 首先定义一个queue切片模拟双端队列,一个result数组存放最终的结果
  2. 当遍历到第一个数据1的时候,由于当前queue的长度为0,直接将1放入队列,queue[1],result[]
  3. 当遍历第二个数据3,由于当前queue的长度不为零,需要比较替换出最大值,queue[3],result[]
  4. 当遍历第三个数据-1,由于queue的长度不为零,需要比较,由于-1<3,则,不进行替换,直接追加到队列的末尾,queue[3,-1],由于此时完成了一组窗口,则result存放queue中的最大值,result[3]
  5. 当遍历到第四个数据-3,同理直接追加到queue[3,-1,-3],同时追加最大值到result[3,3]
  6. 当遍历到第五个数据5,同理,queue将被替换成queue[5],需要注意的是如果第5个数据是2,队列中此时是queue[3,2],此时要维护队列的最大值,规律如下:2对应的索引为i,由于queue[0] == nums[i-k],代表窗口已经移动到不包括之前一组的最大数据,此时queue应去除掉最开始的元素queue=[1:]
  7. 按照以上规律进行循环遍历比较

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxSlidingWindow(nums []int, k int) []int {
if len(nums) == 0 {
return []int{}
}
// 使用切片模拟双端队列
queue := []int{}
result := []int{}
for i := range nums {
for i > 0 && len(queue) > 0 && nums[i] > queue[len(queue)-1] {
queue = queue[:len(queue)-1]
}
queue = append(queue, nums[i])
// 维护队列最大值
// queue[0] == nums[i-k]代表已经遍历完了当前窗口大小的一组数据
if i >= k && queue[0] == nums[i-k] {
queue = queue[1:]
}
if i >= k-1 {
result = append(result, queue[0])
}
}
return result
}