leetcode-239. 滑动窗口最大值

题目描述

给你一个整数数组 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]

思路

单调队列，参考：代码随想录

需自己构建一个队列，写清楚pop，push，front3个函数即可

1）push函数：队列要始终保持一个从大到小的列表，所以push操作的时候，需要把比当前值小的值，pop出去

2）pop函数：滑动窗口，需要逐次把最左边的数排出去；当时当前队列中只保留一部分从大到小的值【有些数在push操作中被去掉了】；所以当要排出去的数和队首的数一样时，则pop()

3）front函数：返回队首元素即可

from collections import dequeclass Myqueue():def __init__(self):self.queue = deque()def push(self, x):while self.queue and x>self.queue[-1]: # 这里是-1，一点点去掉self.queue.pop()self.queue.append(x)def pop(self, x):if self.queue and x==self.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))