剑指Offer系列之「滑动窗口的最大值」

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度的时候，返回空

方法一：暴力法

import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int[] num, int size){ int len = num.length; ArrayList<Integer> res = new ArrayList<>(); if(num.length == 0 || size > len || size < 1) return res; for(int left = 0; left <= len-size; left++){ int right = left + size -1; res.add(maxOfArr(num, left, right)); } return res; } //求一个窗口中的最大值 private static int maxOfArr(int[] arr, int startIndex, int endIndex){ int max = -1; for(int i=startIndex; i<=endIndex; i++){ max = Math.max(max, arr[i]); } return max; } }

时间复杂度：O(n*k)，其中n为数组大小，k为窗口大小 空间复杂度：O(1)，存结果必须要开的数组不算入额外空间

方法二：大顶堆

思路：用一个大顶堆，保存当前滑动窗口中的数据。滑动窗口每次移动一格，就将前面一个数出堆，后面一个数入堆。

import java.util.*; public class Solution { public PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>((o1,o2)->o2-o1);//大顶堆 public ArrayList<Integer> result = new ArrayList<Integer>(); public ArrayList<Integer> maxInWindows(int [] num, int size){ if(num == null || num.length <= 0 || size <= 0 || size > num.length){ return result; } int count = 0; for(;count<size;count++){ //初始化滑动窗口 maxQueue.offer(num[count]); } while(count<num.length){ //对每次操作，找到最大值（用优先队列的大顶堆），然后向后滑动（出堆一个，入堆一个） result.add(maxQueue.peek()); maxQueue.remove(num[count-size]); maxQueue.offer(num[count]); count++; } result.add(maxQueue.peek()); //最后一次入堆后没保存结果，这里额外做一次即可 return result; } }

remove(Object o)的时间复杂度为O(k)；offer()的时间复杂度为O(logk)，k为窗口大小

所以最后时间复杂度为O( n(k+logk) )，即O(n*k)

时间复杂度：O(n*k)

空间复杂度：O(n)

方法三：单调队列

维护一个单调递减的双端队列，Java中双端队列的实现是Deque，Java关于Deque的使用

注意：这里队列中存放的不是元素的值，而是元素在数组中的索引

import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size){ ArrayList<Integer> res = new ArrayList<>(); int len = num.length; if(num == null || len == 0 || size > len || size < 1) return res; Deque<Integer> deque = new LinkedList<>(); for(int i = 0; i < len; i++){ while(!deque.isEmpty() && num[deque.peekLast()] < num[i]){ deque.pollLast(); } deque.offerLast(i); if(deque.peekFirst() + size <= i){ deque.pollFirst(); } if(i + 1 >= size){ res.add(num[deque.peekFirst()]); } } return res; } }

时间复杂度：O(n)，其中n为数组大小 空间复杂度：O(k)，k为窗口的大小