题目
给你一个整数数组 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 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]
示例 3：
输入：nums = [1,-1], k = 1 输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2 输出：[11]
示例 5：
输入：nums = [4,-2], k = 2 输出：[4]
解答
方法一：利用单调队列
1.利用双端队列记录当前滑动窗口的元素索引
2.队列最左侧元素记录滑动窗口中最大元素的索引
3.遍历数组：
- 如果队列最左侧索引已不在滑动窗口范围内，弹出队列最左侧索引
- 通过循环确保队列的最左侧索引所对应元素值最大
- 新元素入队
- 从第一个滑动窗口的末尾索引开始将最大值存储到结果res中
python写法
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: res = [] queue = collections.deque() for i,num in enumerate(nums): if queue and queue[0]==i-k:#比如上图中,4对应的i=4,k=5,那么i-k=-1 。如果右侧滑到8,那么i-k=0,也就是说2要被去除. queue.popleft() while queue and nums[queue[-1]]<num: queue.pop() queue.append(i) if i>=k-1: res.append(nums[queue[0]]) return res
c++写法
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> res; deque<int> deque; for(int i=0;i<nums.size();i++){ if(!deque.empty()&&deque.front()==i-k){ deque.pop_front(); } while(!deque.empty()&&nums[deque.back()]<nums[i]){ deque.pop_back(); } deque.push_back(i); if(i>=k-1){ res.push_back(nums[deque.front()]); } } return res; } };
java写法
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { LinkedList<Integer> deque=new LinkedList<>(); int[] res=new int[nums.length-k+1]; for(int i=0;i<nums.length;i++){ if(!deque.isEmpty()&&deque.peek()==i-k){ deque.poll(); } while(!deque.isEmpty()&&nums[deque.peekLast()]<=nums[i]){ deque.pollLast(); } deque.addLast(i); if(i>=k-1){ res[i-k+1]=nums[deque.peek()]; } } return res; } }
LinkedList
头部添加addFirst()、尾部添加addLast();
头部删除pollFirst()、尾部删除pollLast()
取头部值peekFirst()、取尾部值peekLast()
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n=nums.length; int[] res=new int[n-k+1]; LinkedList<Integer> deque= new LinkedList<>(); for(int i=0;i<n;i++){ if(!deque.isEmpty()&&i-k==deque.peekFirst()){ deque.pollFirst(); } while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){ deque.pollLast(); } deque.addLast(i); if(i-k+1>=0){ res[i-k+1]=nums[deque.peekFirst()]; } } return res; } }
