大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位刚毕业3年的脉友说最近在字节被末尾淘汰了，入职了华为车bu的od岗，工作一周下来整体还不错。他认为华为的技术沉淀和技术氛围都很好，比去小公司强，而且他刚拒了一家大模型公司后端岗的offer，下定决心在od学技术了。
评论区大部分人还是认为楼主这么好的背景去od有点不可思议，都在劝楼主可以过渡，不要久呆，目前刚去属于蜜月期，过几个月就不会这么认为了。一些人开玩笑说虽然没有笔记本下班后不用处理工作，但是根本下不了班啊。还有一些人认为楼主应该去大模型公司，不过楼主觉得去大模型公司做后端开发没啥前途，在字节的时候就天天crud，学不到啥东西。估计面试官给这位脉友画过饼了，不管怎样，既然选择了就加油干吧。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道华为OD的面试题「滑动窗口最大值」。
题目描述
给你一个整数数组 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++和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 ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
