七十四、滑動(dòng)窗口最值問(wèn)題

「@Author：Runsen」

?

編程的本質(zhì)來(lái)源于算法，而算法的本質(zhì)來(lái)源于數(shù)學(xué)，編程只不過(guò)將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

滑動(dòng)問(wèn)題包含一個(gè)滑動(dòng)窗口，它是一個(gè)運(yùn)行在一個(gè)大數(shù)組上的子列表，該數(shù)組是一個(gè)底層元素集合。一般用來(lái)求最值問(wèn)題。

LeetCode 第 239 題：滑動(dòng)窗口最大值

題目來(lái)源于 LeetCode 上第 239 號(hào)問(wèn)題：滑動(dòng)窗口最大值。題目難度為 Hard 。

給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

輸入:?nums?=?[1,3,-1,-3,5,3,6,7],?和?k?=?3
輸出:?[3,3,5,5,6,7]?
解釋:?

??滑動(dòng)窗口的位置????????????????最大值
---------------????????????????-----
[1??3??-1]?-3??5??3??6??7???????3
?1?[3??-1??-3]?5??3??6??7???????3
?1??3?[-1??-3??5]?3??6??7???????5
?1??3??-1?[-3??5??3]?6??7???????5
?1??3??-1??-3?[5??3??6]?7???????6
?1??3??-1??-3??5?[3??6??7]??????7

看到這個(gè)題之后，第一直覺(jué)就是暴力解法，用兩層循環(huán)依次查詢(xún)滑動(dòng)窗口的最大值，實(shí)現(xiàn)代碼如下。

nums?=?[1,?3,?-1,?-3,?5,?3,?6,?7]
k?=?3
res?=?[]
for?i?in?range(k,?len(nums)?+?1):
????res.append(max(nums[i?-?k:i]))
print(res)??#[3,?3,?5,?5,?6,?7]

但max執(zhí)行效率卻很低，在Leetcode上不能通過(guò)，因此我們需要繼續(xù)找尋新的解決方案。

雙端隊(duì)列

Deque 的含義是 “double ended queue”，即雙端隊(duì)列，它具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。顧名思義，它是一種前端與后端都支持插入和刪除操作的隊(duì)列。

在Python中，我直接使用列表代替雙端隊(duì)列，pop(0)表示前端刪除操作，pop()表示后端刪除操作。

雙端隊(duì)列window記錄滑動(dòng)窗口中元素的索引，隊(duì)列左邊界記錄當(dāng)前滑動(dòng)窗口中最大元素的索引

• 當(dāng)隊(duì)列非空，左邊界出界時(shí)（滑動(dòng)窗口向右移導(dǎo)致的），更新左邊界
• 當(dāng)隊(duì)列非空，將隊(duì)列中索引對(duì)應(yīng)的元素值比 num 小的移除，更新隊(duì)列
• 當(dāng)索引 i 大于 k-1，更新輸出結(jié)果

class?Solution:
????def?maxSlidingWindow(self,?nums:?List[int],?k:?int)?->?List[int]:
????????if?not??nums:?return?[]
????????window?,res?=?[],[]
????????for?i,x?in?enumerate(nums):
????????????#?如果存在窗口?而且窗口的第一個(gè)數(shù)?不在這個(gè)范圍，就出去
????????????if?i?>=?k?and?window[0]?<=?i-k:
????????????????window.pop(0)
????????????#?每次進(jìn)入窗口的和最后一個(gè)比較，如果大了，最后一個(gè)直接刪除
????????????while?window?and?nums[window[-1]]?<=?x:
????????????????window.pop()
????????????#?無(wú)論是不是刪除最后一個(gè)，都要加入x到窗口中
????????????window.append(i)
????????????#?如果出了窗口，就把窗口的頭加入到res中
????????????if?i?>=?k-1:
????????????????res.append(nums[window[0]])
????????return?res

LeetCode 第 3 題 無(wú)重復(fù)字符的最長(zhǎng)子串

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

#?示例?1:
#?輸入:?"abcabcbb"
#?輸出:?3
#解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"abc"，所以其長(zhǎng)度為 3。
#?示例?2:
#?輸入:?"bbbbb"
#輸出:?1
#解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"b"，所以其長(zhǎng)度為 1。
#?示例?3
#?輸入:?"pwwkew"
#輸出:?3
#解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"wke"，所以其長(zhǎng)度為 3。
#請(qǐng)注意，你的答案必須是?子串?的長(zhǎng)度，"pwke"?是一個(gè)子序列，不是子串。

下面我們看看，“滑動(dòng)窗口”如何進(jìn)行字符串處理。結(jié)合題目中的例子“abcabcbb”這個(gè)字符串，我們來(lái)看看如何找它的無(wú)重復(fù)最長(zhǎng)子串。

首先，我們定義窗口的兩端：begin和end，分別表示要找的子串的開(kāi)頭和結(jié)尾。

開(kāi)始的時(shí)候，begin和end都指向0的位置即‘a(chǎn)’，然后end不斷后移（窗口變寬），當(dāng)遇到第二個(gè)‘a(chǎn)’時(shí)（遇見(jiàn)重復(fù)字符）就得到一個(gè)子串，其長(zhǎng)度就是end和begin位置的差。

如何判斷是否遇到了重復(fù)字符‘a(chǎn)’呢？需要一個(gè)字典作為輔助數(shù)據(jù)結(jié)構(gòu)，把end從頭開(kāi)始遇到的每個(gè)字符及其索引位置都放到字典里面，end每次移動(dòng)到新字符就查一下字典即可

class?Solution:
????def?lengthOfLongestSubstring(self,?s:?str)?->?int:
????????#?定義兩個(gè)變量res和start,res用于存儲(chǔ)最長(zhǎng)子字符串的長(zhǎng)度，start存儲(chǔ)無(wú)重復(fù)子串左邊的起始位置。
????????'''
????????然后創(chuàng)建一個(gè)哈希表，遍歷整個(gè)字符串，如果字符串沒(méi)有在哈希表中出現(xiàn)，說(shuō)明沒(méi)有遇到過(guò)該字符，則此時(shí)計(jì)算最長(zhǎng)無(wú)重復(fù)子串，當(dāng)哈希表中的值小于left，說(shuō)明left位置更新了，需要重新計(jì)算最長(zhǎng)無(wú)重復(fù)子串。每次在哈希表中將當(dāng)前字符串對(duì)應(yīng)的賦值加1。
????????:param?s:
????????:return:
????????'''
????????d,?res,?start?=?{},?0,?0
????????for?i,?ch?in?enumerate(s):
????????????if?ch?in?d:
????????????????start?=?max(start,?d[ch]?+?1)
????????????res?=?max(res,?i?-?start?+?1)
????????????d[ch]?=?i
????????return?res

人生最重要的不是所站的位置，而是內(nèi)心所朝的方向。只要我在每篇博文中寫(xiě)得自己體會(huì)，修煉身心；在每天的不斷重復(fù)學(xué)習(xí)中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會(huì)有所收獲，不留遺憾 （作者：Runsen ）

?

本文已收錄 GitHub，傳送門(mén)~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?

Reference