騰訊二面算法題來了~

大家好，我是程序員學長~

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

問題描述

示例：

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

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

分析問題

小trick：因為python中只提供了小頂堆，所以我們需要對元素進行取反處理，例如對于列表[1, -3]，我們對元素進行取反，然后插入小頂堆中，此時堆中是這樣的[-1,3]，我們?nèi)〕龆秧斣?1，然后取反為1，正好可以得到列表中的最大值1。

1. 首先，我們將nums的前3個元素放入優(yōu)先級隊列中，隊首元素下標值index=2>0，在窗口中，所以加入結(jié)果中，此時res=[4]。

   

2. 下一個元素2入隊，此時隊首元素下標index=2>1，在窗口中，所以加入結(jié)果中，此時res=[4,4]。

   

3. 下一個元素6入隊，此時隊首元素下標index=4>2，在窗口中，所以加入結(jié)果中，此時res=[4,4,6]。

   

4. 下一個元素2入隊，此時隊首元素下標index=4>3，在窗口中，所以加入結(jié)果中，此時res=[4,4,6,6]。

   

5. 下一個元素5入隊，此時隊首元素下標index=4=4，在窗口中，所以加入結(jié)果中，此時res=[4,4,6,6,6]。

   

6. 下一個元素1隊列，此時隊首元素下標index=4<5，不在窗口中，所以我們將其彈出，此時隊首元素的下標變?yōu)?span style="color: rgb(61, 167, 66);">6，在窗口中，所以加入結(jié)果中，此時res=[4,4,6,6,6,5]。

   

進階

1. 此時隊列為que空，元素2對應(yīng)的下標0入隊。并且此時未形成窗口，不取值。

   

2. 此時隊列que=[0]，隊尾元素為0，它對應(yīng)數(shù)組中的元素是nums[0] < nums[1]的，所以我們把隊尾0彈出，此時隊列為空，我們將1入隊。并且此時未形成窗口，不取值。

   

3. 此時隊列que=[1]，隊尾元素為1，它對應(yīng)的數(shù)組中的元素是nums[1] < nums[2]的，所以我們把隊尾1彈出，此時隊列為空，我們將2入隊。并且此時隊首元素2在窗口[0,2]中，所以取出隊首元素。

   

4. 此時隊列que=[2]，隊尾元素為2，它對應(yīng)的數(shù)組中的元素是nums[2] > nums[3]的，所以我們將3入隊。并且此時隊首元素2在窗口[1,3]中，所以取出隊首元素。

   

5. 此時隊列que=[2,3]，隊尾元素為3，它對應(yīng)的數(shù)組中的元素是nums[3] < nums[4]的，所以我們把隊尾3彈出，并且此時隊尾元素對應(yīng)的數(shù)組中的元素是nums[2] < nums[4]，所以我們把隊尾2彈出，此時隊列為空，我們將4入隊。并且此時隊首元素4在窗口[2,4]中，所以取出隊首元素。

   

6. 此時隊列que=[4]，隊尾元素為4，它對應(yīng)的數(shù)組中的元素是nums[4] > nums[5]的，所以我們將5入隊。并且此時隊首元素4在窗口[3,5]中，所以我們?nèi)〕鲫犑自亍?/section>

   

7. 此時隊列que=[4，5]，隊尾元素為5，它對應(yīng)的數(shù)組中的元素是nums[5] < nums[6]的，所以我們把隊尾5彈出，此時隊尾元素對應(yīng)的數(shù)組中的元素是nums[4] > nums[6] ，所以我們將6入隊。并且此時隊首元素4在窗口[4，6]中，所以我們?nèi)〕鲫犑自亍?/section>

   

8. 此時隊列que=[4，6]，隊尾元素為6，它對應(yīng)的數(shù)組中的元素是nums[6] > nums[7]的，所以我們將7入隊。而此時隊首元素4不在窗口[5,7]中，所以我們將其移除隊列，此時隊首元素6在窗口[5,7]中，所以我們將其取出。

   

下面我們來看一下代碼實現(xiàn)。

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)

????????#將隊首元素加入結(jié)果中
????????ans?=?[nums[q[0]]]

????????#窗口逐步向右移動
????????for?i?in?range(k,?n):
????????????#如果隊列不為空且比隊尾元素大，將隊尾出隊
????????????while?q?and?nums[i]?>=?nums[q[-1]]:
????????????????q.pop()
????????????#直到隊列為空，或者比隊尾元素小，入隊
????????????q.append(i)
????????????#如果隊首元素不在該窗口內(nèi)，出隊操作
????????????while?q[0]?<=?i?-?k:
????????????????q.popleft()
????????????#將隊首元素加入結(jié)果中
????????????ans.append(nums[q[0]])

????????return?ans


s=Solution()
print(s.maxSlidingWindow([2,3,4,2,6,2,5,1],3))

最后

原創(chuàng)不易！各位小伙伴覺得文章不錯的話，不妨點贊（在看）、留言、轉(zhuǎn)發(fā)三連走起！

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