Sliding Window滑动窗口问题

思路

滑动窗口问题一般题目会很典型，要求我们一直维护一个size为k的window，然后do some operation/calculate something within that window。基本思路就是每次不管三七二十一先把当前新的元素加进来，然后如果有需要(比如有元素过期了）移除出来，这时我们可以确保现在maintain的是一个valid window。真正的logic happens here。

步骤

• 一定先加进元素，这里add operation是每个元素都要加的
• 再移除元素，这里移除是需要满足condition的，只有有元素过期的情况下，才去remove
• 进行calculation，这里进行计算也是需要满足condition的，至于形成一个valid的window之后才可以开始计算，如果窗口还不够size，此时不应该进行计算。

题型

因为我们要maintain一个size为k的window,除了上述的算法层面的操作，我们还需要考虑使用什么容器去hold那些元素。这里常见的容器有:

• Queue (First in First out behavior)
• Deque (双端都可以操作）
• Stack (一般是单调栈的应用）
• Heap（求max/min, first k max/mins, median)

题目

Heap

• Leetcode 295. Find Median from Data Stream
• Find Median from Data Stream Where Integers Are 16-bit
• Leetcode 360. Sliding Window Median

Deque

• Leetcode 239. Sliding Window Maximum
• Sliding Window Maximum for Data Streaming (Facebook店面，这道题和前一题有一个区别就是这里是stream而不是array，所以我们没有index，但是我们可以keep一个count var来作为index，其他一样，还是用deque来做。)

Queue

• LintCode 558. Sliding Window Matrix Maximum(这道题看似是求max,但是和sliding window max不同的是那道题是k个里面求一个最大的，这里是k个数求和求最大，所以其实是sliding window mean的变形，我们只需要queue，根本不需要deque）
• Sliding Window Mean
• Leetcode 362. Design Hit Counter