网站到期时间查询,地方旅游网站模板,网站想做个链接怎么做,兰州做网站多少钱题目描述
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1#xff1a;
输入#xff1a;nums [1,3,-1,-3,5,3,6,…题目描述
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1
输入nums [1,3,-1,-3,5,3,6,7], k 3
输出[3,3,5,5,6,7]
解释
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2
输入nums [1], k 1
输出[1]
思路
单调队列参考代码随想录
需自己构建一个队列写清楚poppushfront3个函数即可
1push函数队列要始终保持一个从大到小的列表所以push操作的时候需要把比当前值小的值pop出去
2pop函数滑动窗口需要逐次把最左边的数排出去当时当前队列中只保留一部分从大到小的值【有些数在push操作中被去掉了】所以当要排出去的数和队首的数一样时则pop()
3front函数返回队首元素即可
from collections import dequeclass Myqueue():def __init__(self):self.queue deque()def push(self, x):while self.queue and xself.queue[-1]: # 这里是-1一点点去掉self.queue.pop()self.queue.append(x)def pop(self, x):if self.queue and xself.queue[0]:self.queue.popleft()def front(self):return self.queue[0]class Solution(object):def maxSlidingWindow(self, nums, k)::type nums: List[int]:type k: int:rtype: List[int]que Myqueue()result []for i in range(k):que.push(nums[i])result.append(que.front())for j in range(k,len(nums)):que.pop(nums[j-k]) # 这里是j-kque.push(nums[j])result.append(que.front())return resultif __name__ __main__:s Solution()nums [1, 3, -1, -3, 5, 3, 6, 7]k 3print(s.maxSlidingWindow(nums, k))
