黃金挑戰(zhàn)：滑動(dòng)窗口與堆結(jié)合
堆的大小一般是有限的，能直接返回當(dāng)前位置下的最大值或者最小值
該特征與滑動(dòng)窗口結(jié)合，可以解決一些特定場(chǎng)景的問(wèn)題
1. 滑動(dòng)窗口與堆問(wèn)題的結(jié)合
LeetCode239
https://leetcode.cn/problems/sliding-window-maximum/
思路分析
對(duì)于最大值，K個(gè)最大這種場(chǎng)景，優(yōu)先隊(duì)列（堆）是首先該考慮的思路。
大根堆可以幫我們實(shí)時(shí)維護(hù)一系列元素的最大值
具體執(zhí)行：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-707185.html
- 先將數(shù)組的前K個(gè)元素放入大根堆中，此時(shí)最大值為堆頂元素
- 每當(dāng)窗口右移時(shí)，將新元素放入大根堆中，此時(shí)最大值可能不在滑動(dòng)窗口中
最大值為滑動(dòng)窗口的前一個(gè)元素，此時(shí)需要將堆頂元素移除，直到堆頂元素在滑動(dòng)窗口中
最大值為滑動(dòng)窗口中的元素，此時(shí)最大值就是堆頂元素 - 為了方便判斷堆頂元素與滑動(dòng)窗口的位置關(guān)系，我們可以在有限隊(duì)列中存儲(chǔ)二元組(num, index)，表示元素 num 在數(shù)組中的下標(biāo)為 index
代碼實(shí)現(xiàn)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-707185.html
import heapq
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
ans = []
# 注意 Python 默認(rèn)的優(yōu)先隊(duì)列是小根堆
# pyhton 中（int,int）可正常比較大小 (1, 0) < (2, 0), (1, 0) < (1, 1)
heap = [(-nums[i], i) for i in range(k)]
heapq.heapify(heap)
ans.append(-heap[0][0])
for i in range(n-k):
heapq.heappush(heap, (-nums[i+k], i+k))
# 移除堆頂元素，直到堆頂元素在滑動(dòng)窗口中
while heap[0][1] <= i:
heapq.heappop(heap)
ans.append(-heap[0][0])
return ans
到了這里，關(guān)于算法通關(guān)村第十六關(guān)：黃金挑戰(zhàn)：滑動(dòng)窗口與堆結(jié)合的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[Go版]算法通關(guān)村第十五關(guān)黃金——繼續(xù)研究超大規(guī)模數(shù)據(jù)場(chǎng)景的問(wèn)題](https://imgs.yssmx.com/Uploads/2024/02/693875-1.png)
![[Go版]算法通關(guān)村第十三關(guān)黃金——數(shù)字?jǐn)?shù)學(xué)問(wèn)題之?dāng)?shù)論問(wèn)題（最大公約數(shù)、素?cái)?shù)、埃氏篩、丑數(shù)）](https://imgs.yssmx.com/Uploads/2024/02/668230-1.png)
