滑动窗口最大值
# LeetCode 239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 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
# 思路解析
最简单的解法就是每次移动窗口就重新计算滑动窗口中的最大值，这样就需要遍历一遍滑动窗口，整个过程下来需要遍历n - k次滑动窗口，每遍历一次的时间复杂度为 O(k) ，所以总的时间复杂度为 O(k·(n - k))。实际上我们是可以通过空间换时间的方式把获取每个窗口中最大值的时间复杂度变成O(1) ，整体的时间复杂度变成O(n)。
下面我们根据题目中的例子nums = [1,3,-1,-3,5,3,6,7]，k = 3，来分析一下整个过程。
对于第一个窗口
[1,3,-1]，很显然3是当前窗口的最大值，而且3和-1都有可能是未来窗口的最大值，所以我们需要把3和-1按照顺序保存下来，暂且把它们先保存到candidate中，candidate = [3,-1]。我们获取当前窗口最大值的时候只需要把candidate最左边的元素返回就可以。滑动窗口向右移一步，窗口中的元素变成
[3,-1,-3]，candidate = [3,-1]中的元素均在当前窗口中，新加入窗口的-3有可能是未来窗口的最大值，并且-3会比-1更晚成为未来窗口的最大值，所以我们把-3加入candidate中，放到-1的右边，candidate = [3,-1,-3]。我们依旧把candidate最左边的元素3作为当前窗口的最大值返回。窗口继续向右移一步，窗口中的元素变成
[-1,-3,5]，candidate = [3,-1,-3]中最左边的3已经不属于当前窗口了，它也不会再是未来窗口的最大值，我们需要从左边把它在candidate中移除，candidate = [-1,-3]。新加入窗口的元素5比candidate中的-3，-1都要大，所以-3和-1也不会再是当前或未来窗口的最大值，我们把-3和-1从右到左 依次在candidate中移除，然后把5加进candidate的右边，candidate = [5]。我们依旧把candidate最左边的元素5作为当前窗口的最大值返回。窗口继续向右移一步，窗口中的元素变成
[-3,5,3]，candidate = [5]中的元素均在当前窗口中，新加入窗口的3有可能是未来窗口的最大值，我们把它加到candidate的右边，candidate = [5，3]。我们依旧把candidate最左边的元素5作为当前窗口的最大值返回。窗口继续向右移一步，窗口中的元素变成
[5,3,6]，新加入窗口的6比candidate = [5，3]中的3，5都要大，所以3和5不会再是当前或未来窗口的最大值，我们把3和5从右到左依次在candidate中移除，然后把6加进candidate的右边，candidate = [6]。我们依旧把candidate最左边的元素6作为当前窗口的最大值返回。窗口继续向右移一步，窗口中的元素变成
[3,6,7]，新加入窗口的7比candidate = [6]中的6要大，所以6不会再是当前或未来窗口的最大值，我们从右边把6在candidate中移除，然后把7加进candidate的右边，candidate = [7]。我们依旧把candidate最左边的元素7作为当前窗口的最大值返回。
通过上面6个步骤我们可以发现：
candidate中的元素从左到右始终保持单调递减。窗口每移动一步我们要从左到右检查
candidate中的元素是否还在当前窗口中，如果不在就移除candidate中对应的元素。然后从右到左把candidate中的元素跟新加入当前窗口的元素对比，看candidate中的元素是否还有可能成为未来窗口的最大值，如果没有可能就移除candidate中对应的元素，然后把新加入窗口的元素加到candidate的最右边。每次从两端调整完
candidate中的元素，candidate最左边的元素就是当前窗口的最大值。
上面的步骤需要对candidate两端都进行操作，数组肯定不是最好的选择，最适合的数据结构就是双端队列，我们可以很方便的从队列的两端存取，删除元素，保证队列中的元素从左到右单调递减。
下面我们给出代码实现。
# C++代码
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> dq;
//前k个元素对应的下标依次入队，保证队列是单调递减的
for (int i = 0; i < k; ++i) {
while (!dq.empty() && nums[i] >= nums[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
}
//队列中最大值放入结果数组
res.push_back(nums[dq.front()]);
for (int i = k; i < nums.size(); ++i) {
//保证队列最前面元素在当前的窗口中
while (!dq.empty() && i - dq.front() > k - 1) {
dq.pop_front();
}
//把窗口中的最后一个元素对应的下标从后面放入队列，保证队列的单调递减
while (!dq.empty() && nums[i] >= nums[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
//队列中最大值放入结果数组
res.push_back(nums[dq.front()]);
}
return res;
}
};
# java代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
// 前k个元素对应的下标依次入队，保证队列是单调递减的
for (int i = 0; i < k; i++) {
while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offerLast(i);
}
// 队列中最大值放入结果数组
res[0] = nums[dq.peekFirst()];
for (int i = k; i < nums.length; i++) {
// 保证队列最前面元素在当前的窗口中
while (!dq.isEmpty() && i - dq.peekFirst() >= k) {
dq.pollFirst();
}
// 把窗口中的最后一个元素对应的下标从后面放入队列，保证队列的单调递减
while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offerLast(i);
// 队列中最大值放入结果数组
res[i - k + 1] = nums[dq.peekFirst()];
}
return res;
}
}
# python代码
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
dq = deque()
# 前k个元素对应的下标依次入队，保证队列是单调递减的
for i in range(k):
while dq and nums[i] >= nums[dq[-1]]:
dq.pop()
dq.append(i)
# 队列中最大值放入结果数组
res.append(nums[dq[0]])
for i in range(k, len(nums)):
# 保证队列最前面元素在当前的窗口中
while dq and i - dq[0] > k - 1:
dq.popleft()
# 把窗口中的最后一个元素对应的下标从后面放入队列，保证队列的单调递减
while dq and nums[i] >= nums[dq[-1]]:
dq.pop()
dq.append(i)
# 队列中最大值放入结果数组
res.append(nums[dq[0]])
return res
# 复杂度分析
时间复杂度： 只需要遍历一遍数组，双端队列存取都是常量的时间复杂度，所以时间复杂度为O(n)，其中n是数组的长度。
空间复杂度： 需要借助一个双端队列和一个结果数组，对列中最多有k个元素，结果数组中有n - k个元素，所以空间复杂度为O(n)，其中n是数组的长度，k为滑动窗口的长度。