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

大家好，我是程序员学长~

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3b13f8ce-49f2-46c1-8032-f56e65cacc0f

问题描述

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

示例：

输入：[2，3，4，2，6，2，5，1]，3

输出：[4，4，6，6，6，5]

分析问题

这道题的关键点在于求滑动窗口中的最大值。大小为k的滑动窗口，我们可以通过遍历的方式来求出其中的最大值，需要O(k)的时间复杂度。对于大小为n的数组nums，一共有n-k+1个窗口，因此该算法的时间复杂度是O(nk)。

通过观察，我们可以知道，对于两个相邻的滑动窗口，有k-1个元素是共用的，只有一个元素是变化的，因此我们可以利用此性质来优化我们的算法。

对于求最大值问题，我们可以使用优先级队列（大顶推）来求解。首先，我们将数组的前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

进阶

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c68ac369-4406-4e08-a090-72d826deaa4a

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:bdb74492-b1cb-4c2c-b132-e03e161cfa4a

我们还是以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]中，所以我们将其取出。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:0295ed8e-1849-4e6f-8422-0333e8806b24

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)) < code></=>

最后

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b4d5c4f5-9481-4934-8ed3-1c6174cfe8fa

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:822e3a51-7fe0-4d10-8355-41f3c2a511f6

Original: https://www.cnblogs.com/cxyxz/p/15533196.html
Author: 算法推荐管
Title: 腾讯面试题-求滑动窗口的最大值