腾讯二面算法题来了~
JavaEdge
共 2465字，需浏览 5分钟
·
2021-11-20 23:59
大家好，我是程序员学长~
今天给大家分享一道腾讯面试算法真题，如果喜欢，记得点个关注哟~
问题描述
示例：
输入：[2，3，4，2，6，2，5，1]，3
输出：[4，4，6，6，6，5]
分析问题
小trick：因为python中只提供了小顶堆，所以我们需要对元素进行取反处理，例如对于列表[1, -3]，我们对元素进行取反，然后插入小顶堆中，此时堆中是这样的[-1,3]，我们取出堆顶元素-1，然后取反为1，正好可以得到列表中的最大值1。
首先，我们将nums的前3个元素放入优先级队列中，队首元素下标值index=2>0，在窗口中，所以加入结果中，此时res=[4]。 
下一个元素2入队，此时队首元素下标index=2>1，在窗口中，所以加入结果中，此时res=[4,4]。 
下一个元素6入队，此时队首元素下标index=4>2，在窗口中，所以加入结果中，此时res=[4,4,6]。 
下一个元素2入队，此时队首元素下标index=4>3，在窗口中，所以加入结果中，此时res=[4,4,6,6]。 
下一个元素5入队，此时队首元素下标index=4=4，在窗口中，所以加入结果中，此时res=[4,4,6,6,6]。 
下一个元素1队列，此时队首元素下标index=4<5，不在窗口中，所以我们将其弹出，此时队首元素的下标变为6，在窗口中，所以加入结果中，此时res=[4,4,6,6,6,5]。 
进阶
此时队列为que空，元素2对应的下标0入队。并且此时未形成窗口，不取值。 
此时队列que=[0]，队尾元素为0，它对应数组中的元素是nums[0] < nums[1]的，所以我们把队尾0弹出，此时队列为空，我们将1入队。并且此时未形成窗口，不取值。 
此时队列que=[1]，队尾元素为1，它对应的数组中的元素是nums[1] < nums[2]的，所以我们把队尾1弹出，此时队列为空，我们将2入队。并且此时队首元素2在窗口[0,2]中，所以取出队首元素。 
此时队列que=[2]，队尾元素为2，它对应的数组中的元素是nums[2] > nums[3]的，所以我们将3入队。并且此时队首元素2在窗口[1,3]中，所以取出队首元素。 
此时队列que=[2,3]，队尾元素为3，它对应的数组中的元素是nums[3] < nums[4]的，所以我们把队尾3弹出，并且此时队尾元素对应的数组中的元素是nums[2] < nums[4]，所以我们把队尾2弹出，此时队列为空，我们将4入队。并且此时队首元素4在窗口[2,4]中，所以取出队首元素。 
此时队列que=[4]，队尾元素为4，它对应的数组中的元素是nums[4] > nums[5]的，所以我们将5入队。并且此时队首元素4在窗口[3,5]中，所以我们取出队首元素。 
此时队列que=[4，5]，队尾元素为5，它对应的数组中的元素是nums[5] < nums[6]的，所以我们把队尾5弹出，此时队尾元素对应的数组中的元素是nums[4] > nums[6] ，所以我们将6入队。并且此时队首元素4在窗口[4，6]中，所以我们取出队首元素。 
此时队列que=[4，6]，队尾元素为6，它对应的数组中的元素是nums[6] > nums[7]的，所以我们将7入队。而此时队首元素4不在窗口[5,7]中，所以我们将其移除队列，此时队首元素6在窗口[5,7]中，所以我们将其取出。 
下面我们来看一下代码实现。
import collections
class Solution:
def maxSlidingWindow(self, nums, k):
n = len(nums)
#申请一个双端队列
q = collections.deque()
#初始化第一个窗口
for i in range(k):
#如果队列不为空且比队尾元素大，将队尾出队
while q and nums[i] >= nums[q[-1]]:
q.pop()
#直到队列为空，或者比队尾元素小，入队
q.append(i)
#将队首元素加入结果中
ans = [nums[q[0]]]
#窗口逐步向右移动
for i in range(k, n):
#如果队列不为空且比队尾元素大，将队尾出队
while q and nums[i] >= nums[q[-1]]:
q.pop()
#直到队列为空，或者比队尾元素小，入队
q.append(i)
#如果队首元素不在该窗口内，出队操作
while q[0] <= i - k:
q.popleft()
#将队首元素加入结果中
ans.append(nums[q[0]])
return ans
s=Solution()
print(s.maxSlidingWindow([2,3,4,2,6,2,5,1],3))
最后
原创不易！各位小伙伴觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！
你知道的越多，你的思维越开阔。我们下期再见。
评论