综述

滑动窗口类题目主要有两类， 一类是借助双指针的思想，另一类是需要用到特定的数据结构，如双向链表等，题目主要以数组和字符串为主，都离不开主数组和子数组（主字符串和子字符串）的关系，题眼如“寻找符合某条件的最小长度的子字符串”等

LeetCode 239 滑动窗口最大值

题目链接

链接：LeetCode链接

题目描述

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

示例:
输入: 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

分析

数组nums长度为N，窗口大小为k，则共产生N-k+1个窗口，共有N-k+1个窗口的最大值

解法

解法一 暴力法

遍历数组，找到每个窗口中的最大值存入结果数组中。
时间复杂度：O(Nk)
空间复杂度：O(N-k+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] violentMethod(int[] array, int sizeOfWindow)
{
    int numOfSlide = array.length - sizeOfWindow + 1;
    int[] maxWindowArray = new int[numOfSlide];
    for (int i = 0; i < numOfSlide; i++)
    {
        maxWindowArray[i] = getMaxValue(Arrays.copyOfRange(array, i, i + sizeOfWindow));
    }
    return maxWindowArray;
}

private int getMaxValue(int[] value)
{
    return Arrays.stream(value).max().orElseThrow(IllegalStateException::new);
}

解法二 双端队列

Java中的LinkedList是双端队列，这个数据结构可以从两端以常数时间压入/弹出元素。
具体来说：
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。

分析：
这个双端队列用于存放数组的索引下标，之所以存储索引而不是实际的数，是因为要通过索引之间的关系与窗口大小进行比较，方便判断是否在窗口的范围内。
该双端队列是从头部到尾部单调递减的，并且队列中的所有元素要时刻保持在窗口范围内。
在遍历数组的过程中，队列始终保证头部元素是最大的值，因此，当判断窗口大小满足时只需直接取出队列头部索引，找到数组对应的数即是这次窗口中的最大值了。

算法思路：
刚开始时有一个形成窗口的过程。
队列单调递减，一开始队列为空，第一个元素直接加入到队列中，然后窗口右边界右移，如果当前遍历到的数的值比队列的尾部元素要小，直接加入队尾，如果比队列尾部元素要大，则从队列尾部开始弹出元素，直到队列尾部元素比当前遍历到的元素要大为止，因为需要维护队列的单调性。
此外，在遍历到每一个元素的时候，还要判断当前队列的首部元素是否已经离开窗口了，若是则需要将首部元素从队列首部弹出。

示例：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

初始状态：队列：{}
i=0,nums[0]=1。队列为空,直接加入。队列：{1}
i=1,nums[1]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：{3}
i=2,nums[2]=-1。队尾值为3，-1<3，直接加入。队列：{3,-1}。此时窗口已经形成，L=0,R=2，result=[3]
i=3,nums[3]=-3。队尾值为-1，-3<-1，直接加入。队列：{3,-1,-3}。队首3对应的下标为1，L=1,R=3，有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3，5>-3，依次弹出后加入。队列：{5}。此时L=2,R=4，有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5，3<5，直接加入。队列：{5,3}。此时L=3,R=5，有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3，6>3，依次弹出后加入。队列：{6}。此时L=4,R=6，有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6，7>6，弹出队尾值后加入。队列：{7}。此时L=5,R=7，有效。result=[3,3,5,5,6,7]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int[] maxSlidingWindow(int[] array, int sizeOfWindow)
{
    if (array == null || array.length == 0 || sizeOfWindow < 1 || array.length < sizeOfWindow)
    {
        throw new IllegalArgumentException();
    }
    LinkedList<Integer> indexOfMaxValueDeque = new LinkedList<>();
    int[] maxValueInEachSlideArray = new int[array.length - sizeOfWindow + 1];
    int arrayPointer = 0;
    for (int i = 0; i < array.length; i++)
    {
        while (!indexOfMaxValueDeque.isEmpty() && array[indexOfMaxValueDeque.peekLast()] <= array[i])
        {
            indexOfMaxValueDeque.pollLast();
        }
        indexOfMaxValueDeque.addLast(i);

        // 检查队列中的元素数量是否达到窗口值了，要弹出了
        if (indexOfMaxValueDeque.peekFirst() == i - sizeOfWindow)
        {
            indexOfMaxValueDeque.pollFirst();
        }

        // 检查是否满足窗口大小，要计算最大值了
        if (i >= sizeOfWindow - 1)
        {
            maxValueInEachSlideArray[arrayPointer++] = array[indexOfMaxValueDeque.peekFirst()];
        }
    }
    return maxValueInEachSlideArray;
}

解法三： 动态规划

暂时略

参考链接

[1]LeetCode题解
[2]滑动窗口模板
[3]Leetcode刷题总结之滑动窗口法（尺取法）
[4]算法与数据结构（一）：滑动窗口法总结
[5]【leetcode】滑动窗口法训练