239.滑動窗口最大值
難度：困難
題目
給你一個整數(shù)數(shù)組 nums野哭，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口內(nèi)的 k 個數(shù)字幻件〔η滑動窗口每次只向右移動一位。
返回滑動窗口中的最大值绰沥。
提示：
- 1 <= nums.length <= 10 ^ 5
- -10 ^ 4 <= nums[i] <= 10 ^ 4
- 1 <= k <= nums.length
示例
示例 1：
輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動窗口的位置 最大值
--------------- -----
[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
示例 2：
輸入：nums = [1], k = 1
輸出：[1]
示例 3：
輸入：nums = [1,-1], k = 1
輸出：[1,-1]
示例 4：
輸入：nums = [9,11], k = 2
輸出：[11]
示例 5：
輸入：nums = [4,-2], k = 2
輸出：[4]
分析
暴力解題
除非拿到題目篱蝇，你一眼就能看到該用什么方法來解決，不然先嘗試暴力也不失為一種方法徽曲。
首先如果我們想暴力解題零截，從零開始依次獲取nums長度為K的子數(shù)組，然后求最大值秃臣。
由于1 <= K <= N 10 ^ 5 ,需要計算（N - K） * K涧衙，即N * K = 10 ^ 10次必然要超時。
那能否適當(dāng)優(yōu)化奥此，使得暴力有通關(guān)的可能弧哎？
遍歷數(shù)組N是沒辦法避免的，所以只能在長度為K的子數(shù)組獲取最大值方面入手優(yōu)化了稚虎。
- 首先撤嫩，我們需要創(chuàng)建一個ret數(shù)組用于返回結(jié)果
- 之后，維護一個cur記錄當(dāng)前最大值
- 使用哈希表進行添加刪除操作與查詢操作蠢终，可以適當(dāng)?shù)膲嚎s時間
- 當(dāng)下標(biāo)小于K- 1時序攘，默認(rèn)添加至r哈希表
- 若本次掃描的元素比cur大時鸭限，更新cur，然后將cur加入ret中
- 此時两踏，我們該刪除滑窗左邊界的值了败京，若左邊界刪除后元素 == 0，則刪掉這個鍵
- 如果左邊界的值等于cur梦染，則需要重新掃描一次哈希表求最大值
- 最終返回ret
通過上面的適當(dāng)優(yōu)化赡麦，我們可以壓線通關(guān)。至于復(fù)雜度只能說在N * K的基礎(chǔ)上略有縮減帕识，且跟用例有關(guān)
- 時間復(fù)雜度： 最優(yōu)復(fù)雜度泛粹，即nums為遞增數(shù)組，則復(fù)雜度為O(N),最壞為O(NK)
- 空間復(fù)雜度： O(K)
雙端隊列
暴力解題中我們使用了哈希表和臨時變量來每次更新最大值肮疗，有沒有更為簡潔的辦法呢晶姊？
大家如果之前做過 739.每日溫度 這道題目，就會有單調(diào)棧的這個思路了伪货，唯一不同的是们衙，這道題目固定了長度K，所以單純使用棧不行了碱呼，替換成雙端隊列即可蒙挑。
- 我們創(chuàng)建一個雙端隊列q ,以及待返回的數(shù)組ret
- 在遍歷數(shù)組的過程中，將元素添加至隊列q中愚臀，當(dāng)然添加不是無條件的
- 當(dāng)隊列不為空忆蚀，且隊尾元素比當(dāng)前遍歷的元素小時，隊尾出隊
- 當(dāng)對列q[0] 下標(biāo)小于等于 i - k 時姑裂，表示滑窗左邊界溢出了馋袜，我們需要隊首出隊
- 執(zhí)行完3 雹洗、 4 步后棵里，q[0]為當(dāng)前隊列最大的值咆贬，將nums[q[0]]加入ret
- 最終返回ret即可
- 時間復(fù)雜度： O(N)
- 空間復(fù)雜度： O(K)
堆/優(yōu)先隊列
看到K個最大/小枪眉、前K個 等包含K這個關(guān)鍵字的時候，其實我們應(yīng)該第一時間想到堆這個操作示罗。
之前整理過關(guān)于K的文章： K個數(shù)督赤、K個點、K個元素呀忧，3K堆排序，類比同類三解題溃睹！
同樣的而账，這道題我們可以將上面的雙端隊列替換為優(yōu)先隊列的數(shù)據(jù)結(jié)構(gòu)完成解題。
代碼幾乎沒什么大的差別因篇，只需要注意下Python不支持大根堆泞辐，入堆時使用-num即可笔横。
同時為了快速獲取元素下標(biāo)，需要入堆[-num, index]這樣的結(jié)構(gòu)咐吼。
- 時間復(fù)雜度： O(Nlog(N))
- 空間復(fù)雜度： O(N)
解題
暴力解題:
class Solution:
def maxSlidingWindow(self, nums, k):
if k == 1:
return nums
dic, cur, ret = defaultdict(int), nums[0], []
for i, j in enumerate(nums):
dic[nums[i]] += 1
if i < k - 1:
cur = max(cur, j)
continue
if nums[i] > cur:
cur = nums[i]
ret.append(cur)
left = nums[i - k + 1]
dic[left] -= 1
if dic[left] == 0:
del dic[left]
if left == cur:
cur = max(dic)
return ret
雙端隊列:
class Solution:
def maxSlidingWindow(self, nums, k):
q, ret = deque(), []
for i, j in enumerate(nums):
while q and nums[q[-1]] < j:
q.pop()
if q and q[0] <= i - k:
q.popleft()
q.append(i)
if i >= k - 1:
ret.append(nums[q[0]])
return ret
堆/優(yōu)先隊列
class Solution:
def maxSlidingWindow(self, nums, k):
hp, ret = [], []
for i, j in enumerate(nums):
while hp and hp[0][1] <= i - k:
heapq.heappop(hp)
heapq.heappush(hp, [-j, i])
if i >= k - 1:
ret.append(-hp[0][0])
return ret
歡迎關(guān)注我的公眾號: 清風(fēng)Python吹缔，帶你每日學(xué)習(xí)Python算法刷題的同時，了解更多python小知識锯茄。
我的個人博客：https://qingfengpython.cn
