剑指Offer(六十四)滑动窗口的最大值(Java版)
描述
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ,找出所有滑动窗口里数值的最大值。
例如,如果输入数组{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]}。
窗口大于数组长度或窗口长度为0的时候,返回空。
数据范围: 1 le n le 100001 n 10000,0 le size le 100000 size 10000,数组中每个元素的值满足 |val| le 10000 val 10000
要求:空间复杂度 O(n) O ( n ),时间复杂度 O(n) O ( n ) 示例1
输入:[2,3,4,2,6,2,5,1],3
返回值:[4,4,6,6,6,5] 示例2
输入:[9,10,9,-7,-3,8,2,-6],5
返回值:[10,10,9,8] 示例3
输入:[1,2,3,4],5
返回值:[]第一种解法
直接从零开始,遍历即可,组成一个滑动窗口,然后从滑动窗口中,找出最大的一个值即可,此方法属于暴力解法。代码如下public ArrayList firstMaxInWindows(int [] num, int size) { ArrayList list = new ArrayList<>(); if(num == null || num.length < 1 || size < 1 || num.length < size){ return list; } for (int i = 0; i < num.length; i++) { if(i + size <= num.length){ ArrayList listTmp = new ArrayList<>(); for (int j = 0; j < size; j++) { listTmp.add(num[j+i]); } Collections.sort(listTmp); list.add(listTmp.get(size-1)); } } return list; }第二种解法
在第一种解法里面,进行了一点小优化,不再用新的集合保存滑动窗口的所有数据,只保存滑动窗口里最大的一个值即可。代码如下public ArrayList secondMaxInWindows(int [] num, int size) { ArrayList list = new ArrayList<>(); if(num == null || num.length < 1 || size < 1 || num.length < size){ return list; } for (int i = 0; i <= num.length-size; i++) { int max = num[i]; for (int j = i; j < i+size; j++) { if(max < num[j]){ max = num[j]; } } list.add(max); } return list; }