大家好，我就是那个在B站讲算法的「华南溜达虎」。
工资一般是比较敏感的话题，大多数公司都是禁止互相打听薪资的，这样可以避免员工之间的不满和竞争，从而维持团队的和谐。今天看到一位脉友无意间得知同事的工资比他多了3000，他俩工作内容差不多，并且他负责的模块还比这个同事多了几个，很久了都没涨过工资，越想心理越不平衡，直接想摆烂了。
有脉友认为工资一旦透明员工就不那么好忽悠了，也有脉友认为工资保密类似于给驴戴上眼罩。大家觉得工资有必要保密吗？
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「滑动窗口最大值」。
题目描述
给你一个整数数组 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 + 1次滑动窗口，每遍历一次的时间复杂度为 O(k) ，所以总的时间复杂度为 O(k·(n - k + 1))。实际上我们是可以通过空间换时间的方式把获取每个窗口中最大值的时间复杂度变成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++和python的两种代码实现。
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;
}
};
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为滑动窗口的长度。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
