Study Plan For Algorithms - Part35

1. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
方法一：

def maxSlidingWindow(nums, k):queue = []res = []if not nums:return queuefor r in range(len(nums)):l = r - k + 1if l > 0 and queue[0] == nums[l - 1]:queue.pop(0)while queue and queue[-1] < nums[r]:queue.pop()queue.append(nums[r])if l >= 0:res.append(queue[0])return res

方法二：

import heapqdef maxSlidingWindow(nums, k):n = len(nums)res = []window = []for i in range(n):heapq.heappush(window, (-nums[i], i))if window[0][1] <= i - k:heapq.heappop(window)if i >= k - 1:res.append(-window[0][0])return res

方法三：

def maxSlidingWindow(nums, k):n = len(nums)res = []for i in range(n - k + 1):max_val = nums[i]for j in range(i, i + k):max_val = max(max_val, nums[j])res.append(max_val)return res