给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值。
思路 1: 堆/优先队列
维护一个最大堆保存窗口内的值;
难点是如何保证堆内 (主要是堆顶) 的值正好在窗口内;
方法是同时保存值的索引, 利用索引判断当前堆顶值是否在窗口内, 详见代码;
Python
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
import heapq
h = []
for i in range(k):
heapq.heappush(h, (-nums[i], i))
ret = [-h[0][0]]
for i in range(k, len(nums)):
while h and h[0][1] <= i - k:
heapq.heappop(h)
heapq.heappush(h, (-nums[i], i))
ret.append(-h[0][0])
return ret