滑动窗口算法

滑动窗口操作

• 使用左右指针L、R
• 当一个数进入窗口时，必须从尾部进入，R向右移动一位
• 当一个数出窗口时，必须从头部出去，L向右移动一位
• L、R只能向右移动，且R>L

---

算法原题(滑动窗口的最大值)

Problem

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为[4, 3, 5, 4, 3, 3, 6, 7]，窗口大小为3时：
[4 3 5] 4 3 3 6 7 窗口中最大值为5
4[3 5 4] 3 3 6 7 窗口中最大值为5
4 3[5 4 3] 3 6 7 窗口中最大值为5
4 3 5[4 3 3] 6 7 窗口中最大值为4
4 3 5 4[3 3 6] 7 窗口中最大值为6
4 3 5 4 3[3 6 7] 窗口中最大值为7
如果数组长度为n，窗口大小为w，则一共产生n - w + 1个窗口的最大值。
请实现一个函数。
输入：整型数组arr，窗口大小为w。
输出：一个长度为n - w + 1的数组res，res[i]表示每一种窗口状态下的最大值。
以本题为例，结果应该返回{ 5,5,5,4,6,7 }。

Solution

1. 使用双向链表进行解答（LinkedList）
2. R的操作
   • 保证链表从左到右必须是从大到小，即头节点为最大值
   • 每进入一个数，从链表的尾部进入，一但发现新的值比原来的链表的尾部大，先弹出，直到尾部的值大于即将插入的值，然后插入
   • 每次压入的值都是原数组的下标值
3. L的操作
   • 每一次进行L的操作时，判断链表的头节点是否过期，过期就直接弹出，否则继续向右移动
   • 举例：当窗口的大小size=3，R=4，链表里面有4个数，大于size了，这个时候i=0就过期了，所以直接弹出头节点

Code

import java.util.LinkedList;
import java.util.ArrayList;

/**
 * @author god-jiang
 * @date 2020/1/1
 */
public class maxSlidingWindow {
    public class Solution {
        public ArrayList<Integer> maxInWindows(int[] num, int size) {
            //记录滑动窗口实时的最大值结果
            ArrayList<Integer> list = new ArrayList<>();
            //双向链表，从左到右必须是从大到小的顺序
            LinkedList<Integer> queue = new LinkedList<>();
            int length = num.length;
            if (length < size || size == 0) {
                return list;
            }
            for (int i = 0; i < length; i++) {
                //如果链表的尾部小于即将插入的值，则弹出
                while (!queue.isEmpty() && num[queue.peekLast()] <= num[i]) {
                    queue.pollLast();
                }
                //插入只能从尾部插入
                queue.addLast(i);
                //判断链表的头节点是否过期，从头部弹出
                if (i - queue.peekFirst() == size) {
                    queue.pollFirst();
                }
                //当达到滑动窗口的size时，进行收集结果
                if (i >= size - 1) {
                    list.add(num[queue.peekFirst()]);
                }
            }
            return list;
        }
    }
}

Test

---

总结

以上就是滑动窗口最大值的解法，在leetcode上是属于困难难度的一道题目，但是你掌握了滑动窗口算法，加一些边界的判断就可以轻松拿下

参考链接

• 一笔一画一人生
• 经典算法总结