201010剑指Offer学习总结：滑动窗口
20201010算法学习总结：滑动窗口
1. 什么是滑动窗口
滑动窗口就是在一个数组中用矩形框框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优解。
对于这道题来说，数组就是正整数序列 [ 1, 2, 3, … , n ]。我们设滑动窗口的左边界为 i，右边界为 j，则滑动窗口框起来的是一个左闭右开区间 [i, j)。为了编程的方便，滑动窗口一般表示成一个左闭右开区间。
初始时，i=1, j=1，滑动窗口位于序列的最左侧，窗口大小为0。如下图所示的滑动窗口包含元素为2、3、4。
滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)。（如果左右边界向左移动的话应该叫做“回溯”，算法的时间复杂度就可能不止 O(n)了）
2. 例题一：和为s的连续正数序列
剑指 Offer 57 - II. 和为s的连续正数序列【难度：简单】
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
思路：
在这道题中，我们关注的是滑动窗口中所有数的和。当滑动窗口的右边界向右移动时，也就是 j = j + 1，窗口中多了一个数字 j，窗口的和也就要加上 j。当滑动窗口的左边界向右移动时，也就是 i = i + 1，窗口中少了一个数字 i，窗口的和也就要减去 i。滑动窗口只有右边界向右移动（扩大窗口）和左边界向右移动（缩小窗口） 两个操作。
那么何时应该扩大或者缩小窗口呢？
- 当窗口的和小于
target时，窗口的和需要增加，窗口右边界向右移动； - 当窗口的和大于
target时，窗口的和需要减少，窗口左边界向右移动； - 当窗口的和等于
target时，这时我们已经找到了一个可行解，记录下来窗口[i,j)，接下来应该去找i+1开始的序列了。
代码：
public int[][] findContinuousSequence(int target) {
int i = 1; // 滑动窗口的左边界
int j = 1; // 滑动窗口的右边界
int sum = 0; // 滑动窗口中数字的和
List<int[]> res = new ArrayList<>();
while (i <= target / 2) {
if (sum < target) {
// 右边界向右移动
sum += j;
j++;
} else if (sum > target) {
// 左边界向右移动
sum -= i;
i++;
} else {
// 记录结果
int[] arr = new int[j-i];
for (int k = i; k < j; k++) {
arr[k-i] = k;
}
res.add(arr);
// 左边界向右移动
sum -= i;
i++;
}
}
return res.toArray(new int[res.size()][]);
}
3. 例题二：滑动窗口的最大值
剑指 Offer 59 - I. 滑动窗口的最大值【难度：简单】
给定一个数组 nums 和滑动窗口的大小 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.length-k+1。所以返回的数组结果长度应为此值。
-
使用哪种数据结构来保存窗口的最值，使找出最值能实现O(1)复杂度？
使用单调队列实现。我们只要保证deque始终是非严格递减的（即只保证前一项大于等于后一项的关系），每次都确保最大值在队首，这样直接返回队首就得到最值。
-
窗口移动时怎么处理队列中的值？
当窗口已经建立时，每次移动窗口都会舍弃一个元素（窗口中的第一个元素）、新加入一个元素（窗口后面的第一个元素）。如果当前的队头最值正好是由要舍弃的元素产生的，那么要从队列中删除它。
代码实现如下：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for(int i = 0; i < k; i++) { // 还未形成窗口时
//当队列不为空时，每次都和队列最后一个元素比较，如果比新元素小，就删除它。
while(!deque.isEmpty() && deque.peekLast() < nums[i])
deque.removeLast();
deque.addLast(nums[i]);//把新元素入队
}
res[0] = deque.peekFirst();//第一个滑动窗口的最大值就是队列的首元素
for(int i = k; i < nums.length; i++) { // 形成窗口后
if(deque.peekFirst() == nums[i - k])//每次移动窗口都会删除窗口最左侧元素，即下标i-k的元素，如果队头也等于这个元素就要一起删掉
deque.removeFirst();
//当队列不为空时，每次都和队列最后一个元素比较，如果比新元素小，就删除它。
while(!deque.isEmpty() && deque.peekLast() < nums[i])
deque.removeLast();
deque.addLast(nums[i]);//从队尾加入新元素
res[i - k + 1] = deque.peekFirst();//记录本次滑动窗口中的最值。
}
return res;
}
}