滑动窗口最大值-leetcode 239题

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
解法一：暴力法：
解题思路：

移动窗口计算每一个窗口的最大值

将步骤1得到的值加入要返回的列表中

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:# 暴力法时间复杂度O（Nk） 直接超出时间限制res = []if k<1 or k>len(nums):return res left = 0right = k - 1while right<len(nums):maxval = self.maxvalue(left,right,nums)res.append(maxval)left += 1right += 1return resdef maxvalue(self,left,right,nums):maxval = nums[left]while left<=right:if maxval<nums[left]:maxval = nums[left]return maxval

解法二：单调队列法
解题思路：

如果队列最左侧索引已不在滑动窗口范围内，弹出队列最左侧索引

通过循环确保队列的最左侧索引所对应元素值最大

新元素入队

从第一个滑动窗口的末尾索引开始将最大值存储到结果res中

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:# 边界条件if k * len(nums) == 0:return []# 优化if k == 1:return numsfrom collections import dequeq = deque()# 单调队列法：def clean_q()这个函数是精髓def clean_q(i):while q and q[0] <= i-k:q.popleft()while q and nums[q[-1]] < nums[i]:q.pop()q.append(i)res = []for i in range(k):clean_q(i)res.append(nums[q[0]])for i in range(k,len(nums)):clean_q(i)res.append(nums[q[0]])return res

总结

以上是生活随笔为你收集整理的滑动窗口最大值-leetcode 239题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。