腾讯面试题-求滑动窗口的最大值

2021年11月26日 阅读数:1
这篇文章主要向大家介绍腾讯面试题-求滑动窗口的最大值,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

你们好,我是程序员学长~python

今天给你们分享一道腾讯面试真题,若是喜欢,记得点个关注哟~程序员

问题描述

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只能够看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。面试

示例:算法

输入:[2,3,4,2,6,2,5,1],3数组

输出:[4,4,6,6,6,5]app

分析问题

这道题的关键点在于求滑动窗口中的最大值。大小为k的滑动窗口,咱们能够经过遍历的方式来求出其中的最大值,须要O(k)的时间复杂度。对于大小为n的数组nums,一共有n-k+1个窗口,所以该算法的时间复杂度是O(nk)。优化

经过观察,咱们能够知道,对于两个相邻的滑动窗口,有k-1个元素是共用的,只有一个元素是变化的,所以咱们能够利用此性质来优化咱们的算法。code

对于求最大值问题,咱们可使用优先级队列(大顶推)来求解。首先,咱们将数组的前k个元素放入优先级队列中。每当咱们向右移动窗口时,咱们就能够把一个新的元素放入队列中,此时堆顶元素就是堆中全部元素的最大值,然而这个最大值有可能不属于当前的滑动窗口中,咱们须要将该元素进行移除处理(若是最大值不在当前滑动窗口中,它只能在滑动窗口的左边界的左侧,因此滑动窗口向右移动的过程当中,该元素不再会出如今滑动窗口中了,因此咱们能够对其进行移除处理)。咱们不断地移除堆顶的元素,直到其确实出如今滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。排序

为了方便判断堆顶元素与滑动窗口的位置关系,咱们能够在优先队列中存储二元组 (num,index),表示元素num在数组中的下标为index。队列

小trick:由于python中只提供了小顶堆,因此咱们须要对元素进行取反处理,例如对于列表[1, -3],咱们对元素进行取反,而后插入小顶堆中,此时堆中是这样的[-1,3],咱们取出堆顶元素-1,而后取反为1,正好能够获得列表中的最大值1。

咱们nums=[2,3,4,2,6,2,5,1],k=3为例,来看一下具体的过程。

  1. 首先,咱们将nums的前3个元素放入优先级队列中,队首元素下标值index=2>0,在窗口中,因此加入结果中,此时res=[4]。

  2. 下一个元素2入队,此时队首元素下标index=2>1,在窗口中,因此加入结果中,此时res=[4,4]。

  3. 下一个元素6入队,此时队首元素下标index=4>2,在窗口中,因此加入结果中,此时res=[4,4,6]。

  4. 下一个元素2入队,此时队首元素下标index=4>3,在窗口中,因此加入结果中,此时res=[4,4,6,6]。

  5. 下一个元素5入队,此时队首元素下标index=4=4,在窗口中,因此加入结果中,此时res=[4,4,6,6,6]。

  6. 下一个元素1队列,此时队首元素下标index=4<5,不在窗口中,因此咱们将其弹出,此时队首元素的下标变为6,在窗口中,因此加入结果中,此时res=[4,4,6,6,6,5]。

进阶

这道题咱们也可使用双端队列来求解。咱们在遍历数组的过程当中,不断的对元素对应的下标进行出队入队操做,在出入队的过程当中,咱们须要保证队列中存储的下标对应的元素是从大到小排序的。具体来讲,当有一个新的元素对应的下标须要入队时,若是该元素比队尾对应的元素的值大,咱们须要弹出队尾,而后循环往复,直到队列为空或者新的元素小于队尾对应的元素。

因为队列中下标对应的元素是严格单调递减的,所以队首下标对应的元素就是滑动窗口中的最大值。可是此时的最大值可能在滑动窗口左边界的左侧,而且随着窗口向右移动,它永远不可能出如今滑动窗口中了。所以咱们还须要不断从队首弹出元素,直到队首元素在窗口中为止。

咱们仍是以nums=[2,3,4,2,6,2,5,1],k=3为例,来看一下具体的过程。咱们首先初始化一个空队列que。

  1. 此时队列为que空,元素2对应的下标0入队。而且此时未造成窗口,不取值。

  2. 此时队列que=[0],队尾元素为0,它对应数组中的元素是nums[0] < nums[1]的,因此咱们把队尾0弹出,此时队列为空,咱们将1入队。而且此时未造成窗口,不取值。

  3. 此时队列que=[1],队尾元素为1,它对应的数组中的元素是nums[1] < nums[2]的,因此咱们把队尾1弹出,此时队列为空,咱们将2入队。而且此时队首元素1在窗口[0,2]中,因此取出队首元素。

  4. 此时队列que=[2],队尾元素为2,它对应的数组中的元素是nums[2] > nums[3]的,因此咱们将3入队。而且此时队首元素1在窗口[1,3]中,因此取出队首元素。

  5. 此时队列que=[2,3],队尾元素为3,它对应的数组中的元素是nums[3] < nums[4]的,因此咱们把队尾3弹出,而且此时队尾元素对应的数组中的元素是nums[2] < nums[4],因此咱们把队尾2弹出,此时队列为空,咱们将4入队。而且此时队首元素4在窗口[2,4]中,因此取出队首元素。

  6. 此时队列que=[4],队尾元素为4,它对应的数组中的元素是nums[4] > nums[5]的,因此咱们将5入队。而且此时队首元素4在窗口[3,5]中,因此咱们取出队首元素。

  7. 此时队列que=[4,5],队尾元素为5,它对应的数组中的元素是nums[5] < nums[6]的,因此咱们把队尾5弹出,此时队尾元素对应的数组中的元素时nums[4] > nums[6] ,因此咱们将6入队。而且此时队首元素4在窗口[4,6]中,因此咱们取出队首元素。

  8. 此时队列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))

最后

原创不易!各位小伙伴以为文章不错的话,不妨点赞(在看)、留言、转发三连走起!

你知道的越多,你的思惟越开阔。咱们下期再见。