滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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.ArrayList; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size){ ArrayList<Integer> list = new ArrayList<>(); if(num == null || num.length == 0 || size == 0)return list; for(int i = 0; i < num.length - size + 1; i++){ int tempMax = num[i]; for(int j = 1;j < size;j++){ if(num[i+j] > tempMax) tempMax = num[i+j]; } list.add(tempMax); } return list; } }

时间复杂度：O(kn)，k为滑动窗口的大小，n为数组的长度

思路二

使用一个双端队列保存有可能成为窗口最大值的数据

这里之所以采用双端队列是因为，当即将进入窗口的数据大于队列中的值，那么队列中的值会依次从尾部进行删除，如果队列头部的数字已经滑出窗口，那么也需要将队列的头部删除，所以我们需要在队列的头部和尾部都进行删除操作，所以需要一个双端队列

import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> windowMax = new ArrayList<>(); // 条件检查 if (num == null || size < 1 || num.length < 1|| size > num.length) { return windowMax; } Deque<Integer> indexQueue = new LinkedList<>(); /** * 窗口还没有被填满时，找最大值的索引 */ for (int i = 0; i < size && i < num.length; i++) { // 如果索引对应的值比之前存储的索引值对应的值大或者相等，就删除之前存储的值 while (!indexQueue.isEmpty() && num[i] >= num[indexQueue.getLast()]) { indexQueue.removeLast(); } // 添加索引 indexQueue.addLast(i); } // 窗口已经被填满了 for (int i = size; i < num.length; i++) { // 第一个窗口的最大值保存 windowMax.add(num[indexQueue.getFirst()]); // 如果新加入窗口的的值比队列中的值大，就删除队列的值 while (!indexQueue.isEmpty() && num[i] >= num[indexQueue.getLast()]) { indexQueue.removeLast(); } // 删除队列中已经滑出窗口的数据对应的下标 if (!indexQueue.isEmpty() && indexQueue.getFirst() <= (i - size)) { indexQueue.removeFirst(); } // 可能的最大的下标索引入队 indexQueue.addLast(i); } // 最后一个窗口最大值入队 windowMax.add(num[indexQueue.getFirst()]); return windowMax; } }