騰訊面試題-求滑動窗口的最大值

大家好，我是程式設計師學長~

今天給大家分享一道騰訊面試真題，如果喜歡，記得點個關注喲~

問題描述

給你一個整數數組 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為例，來看一下具體的過程。

首先，我們將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]。

進階

這道題我們也可以使用雙端隊列來求解。我們在遍曆數組的過程中，不斷的對元素對應的下標進行出隊入隊操作，在出入隊的過程中，我們需要保證隊列中存儲的下標對應的元素是從大到小排序的。具體來說，當有一個新的元素對應的下標需要入隊時，如果該元素比隊尾對應的元素的值大，我們需要彈出隊尾，然後循環往複，直到隊列為空或者新的元素小於隊尾對應的元素。

由於隊列中下標對應的元素是嚴格單調遞減的，因此隊首下標對應的元素就是滑動窗口中的最大值。但是此時的最大值可能在滑動窗口左邊界的左側，並且隨著窗口向右移動，它永遠不可能出現在滑動窗口中了。因此我們還需要不斷從隊首彈出元素，直到隊首元素在窗口中為止。

我們還是以nums=[2，3，4，2，6，2，5，1]，k=3為例，來看一下具體的過程。我們首先初始化一個空隊列que。

此時隊列為que空，元素2對應的下標0入隊。並且此時未形成窗口，不取值。
此時隊列que=[0]，隊尾元素為0，它對應數組中的元素是nums[0] < nums[1]的，所以我們把隊尾0彈出，此時隊列為空，我們將1入隊。並且此時未形成窗口，不取值。
此時隊列que=[1]，隊尾元素為1，它對應的數組中的元素是nums[1] < nums[2]的，所以我們把隊尾1彈出，此時隊列為空，我們將2入隊。並且此時隊首元素1在窗口[0,2]中，所以取出隊首元素。
此時隊列que=[2]，隊尾元素為2，它對應的數組中的元素是nums[2] > nums[3]的，所以我們將3入隊。並且此時隊首元素1在窗口[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))

最後

原創不易！各位小夥伴覺得文章不錯的話，不妨點贊（在看）、留言、轉發三連走起！

你知道的越多，你的思維越開闊。我們下期再見。

Tags: 大廠面試面試演算法系列面試高頻演算法題