滑动窗口的最大值【Java版】
滑动窗口的最大值
http://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788
【总体思路】采用 双端队列ArrayDeque,两端巧妙删除/增加;达到O(N)时间。
import java.util.ArrayList; import java.util.ArrayDeque; //ArrayList有index->value的对应,而ArrayDeque只有值,没有下标,无法随机查找,只能操作两头,但两头高效。 //ArrayDeque类型,双端队列。(只有两头可以读写,中间不能读写查) public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> res = new ArrayList<Integer>(); ArrayDeque<Integer> qmax = new ArrayDeque<Integer>(size);//qmax用于存序号i,而不是存num[i]里面的值。 if(num==null || num.length < size || size<=0)return res;//不能是return null for(int i=0; i<=num.length-1; ++i){ //1.右入qmax while(qmax.peekLast()!=null && num[i] > num[qmax.peekLast()])qmax.removeLast(); //【冒泡排序思想】qmax里面的值,左大右小。//去除num[i]左边相邻连续一排较小值。(新比旧大,旧必无用) qmax.addLast(i);//最右边一格,而不一定和原先的连着?? //2.左出qmax if(qmax.peekFirst() == i-size) qmax.removeFirst();//左框最左才会出 //不是 ==i-size+1 //3.res收当前max if(i>=size-1) res.add(num[qmax.peekFirst()]);//最左边一定是当前的最大值,进入结果数组 } return res; } }//时间O(N) 空间O(N) //最粗犷的方法是O(N*size) //因为有while循环,单轮最多O(size)。但整体平均每轮<=O(1),因为数字不够每轮都O(size)规模删除
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》