Problem: 239. 滑动窗口最大值
题目
输入一个数组nums,滑动窗口k遍历该数组,输出得到的最大值数组;
示例1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
思路
构造一个单调队列表示当前窗口中单调递减的队列,队列的头就是最大值,为保证这个队列是窗口数据的表示,每次判断队首元素是否是i-k,若是,则pop该队首。
复杂度
时间复杂度:
O ( n ) O(n) O(n)
空间复杂度:文章来源:https://www.toymoban.com/news/detail-834610.html
O ( k ) O(k) O(k)文章来源地址https://www.toymoban.com/news/detail-834610.html
Code
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
queue = list()
for i in range(k):
while queue and nums[i] >= nums[queue[-1]]:
queue.pop()
queue.append(i)
ans = [nums[queue[0]]]
for i in range(k, len(nums)):
while queue and nums[i] >= nums[queue[-1]]:
queue.pop()
queue.append(i)
if queue[0] == i -k:
queue.pop(0)
ans.append(nums[queue[0]])
return ans
到了这里,关于单调队列-滑动窗口最大值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!