每日算法系列【LeetCode 239】滑动窗口最大值
题目描述
给定一个数组 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 的实现，如果你不会用的话，也可以用一个数组自己模拟一下，我觉得反而更加方便一点。
公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。
