题目描述
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例1
输入： 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
提示你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
题解
双端单调队列
本题要找长度为 k 的区间的最大值。模拟这个区间的移动过程，可以发现，右边增加一个数，左边必然会去掉一个数。
那么最大的数有什么性质呢？可以发现，如果扫描区间末尾，在已经遍历过的数之中，一个数 a 在 b 前面，并且 a 还比 b 小，那么 a 在之后的区间里永远无法成为最大值。
所以我们遍历到一个数时，它之前的所有比它小的数都可以去掉了，只保留比它大的数就行了。这就让人想到了之前介绍过的单调栈，但是本题中是先进先出，所以要改用单调队列。此外队列末尾不仅要增加元素，还得维护单调递减，适当去除一些元素，所以队列两端都得有插入和删除的功能。所以本题要使用双端队列，而队列中的元素又是单调递减的，所以又是双端单调队列。
这样思路就很明确了：
- 遍历元素 nums[i] ，然后跟队列尾部元素比较，如果比尾部元素大，就出队，然后继续比较，直到 nums[i] 小于尾部元素，然后将它入队。
- 然后用一下队列首部元素的下标，计算出队列中区间的长度，如果大于 k 了，那么队首元素就要出队。
- 最后队首元素就是当前区间的最大值。
分块法
试想如果我们将数组划分为相同大小的若干块，每一块中最大值都是知道的话，那么要求区间最大值，只需要看它在哪几块里就行了。
那么块的大小应该设成多少呢？
如果块大小为 k ，就可以发现长度为 k 的区间 [i, j] 要么正好就是一个完整的块，要么跨越了两个相邻块。那么我们只需要知道 i 到它那块末尾元素中最大值，以及 j 到它那块开头最大值就行了，两个部分合并求最大值就是区间的最大值了。而每个元素到它自己那块的开头和末尾的最大值都可以预处理出来，方法和求前缀和类似。
那为什么块大小不能是其他值呢？如果块大小大于 k ，那么会出现区间完全包含于一块之中的情况，那就和不分块一样了。如果块大小小于 k ，那么就会出现区间横跨了好几块，那么还得遍历中间块的最大值。极端情况下如果块大小为 1 ，那么就等于暴力求解。
代码
双端单调队列（c++）
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); deque<int> Q; vector<int> res; for (int i = 0; i < n; ++i) { while (!Q.empty() && nums[i] >= nums[Q.back()]) Q.pop_back(); Q.push_back(i); if (i - Q.front() + 1 > k) Q.pop_front(); if (i >= k-1) res.push_back(nums[Q.front()]); } return res; } };
双端单调队列+数组实现（c++）
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); vector<int> Q(n, 0); vector<int> res; int l = 0, r = 0; for (int i = 0; i < n; ++i) { while (r-l > 0 && nums[i] >= nums[Q[r-1]]) r--; Q[r++] = i; if (i - Q[l] + 1 > k) l++; if (i >= k-1) res.push_back(nums[Q[l]]); } return res; } };
分块法（c++）
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); vector<int> lmax(n, 0), rmax(n, 0); vector<int> res; if (!n) return res; for (int i = 0; i < n; ++i) { if (i%k == 0) lmax[i] = nums[i]; else lmax[i] = max(lmax[i-1], nums[i]); } for (int i = n-1; i >= 0; --i) { if ((i+1)%k == 0 || i == n-1) rmax[i] = nums[i]; else rmax[i] = max(rmax[i+1], nums[i]); } for (int i = k-1; i < n; ++i) { res.push_back(max(lmax[i], rmax[i-k+1])); } return res; } };
双端单调队列（python）
import collections class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) Q = collections.deque() res = [] for i in range(n): while len(Q) > 0 and nums[i] >= nums[Q[-1]]: Q.pop() Q.append(i) if i - Q[0] + 1 > k: Q.popleft() if i >= k-1: res.append(nums[Q[0]]) return res
双端单调队列+数组实现（python）
import collections class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) Q = [0] * n res = [] l, r = 0, 0 for i in range(n): while r-l > 0 and nums[i] >= nums[Q[r-1]]: r -= 1 Q[r] = i r += 1 if i - Q[l] + 1 > k: l += 1 if i >= k-1: res.append(nums[Q[l]]) return res
分块法（python）
import collections class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) lmax, rmax = [0] * n, [0] * n res = [] if n == 0: return res for i in range(n): if i%k == 0: lmax[i] = nums[i] else: lmax[i] = max(lmax[i-1], nums[i]) for i in range(n-1, -1, -1): if (i+1)%k == 0 or i == n-1: rmax[i] = nums[i] else: rmax[i] = max(rmax[i+1], nums[i]) for i in range(k-1, n): res.append(max(lmax[i], rmax[i-k+1])) return res
后记
双端队列在 c++ 和 python 中都有 deque 的实现，如果你不会用的话，也可以用一个数组自己模拟一下，我觉得反而更加方便一点。
