《数据结构》 (java版) 课件 5-4双端队列的一个例子

课后练习//生成滑动窗口的最大值数组//例如，k=3//4,3,5,4,3,3,6,7//[4,3,5],4,3,3,6,7//4,[3,5,4],3,3,6,7//4,3,[5,4,3],3,6,7//4,3,5,[4,3,3],6,7//4,3,5,4,[3,3,6],7//4,3,5,4,3,[3,6,7]//结果：//5,5,5,4,6,7课后练习

public

static

int[]slideWindowMax(int[]a,int

k){

if(a==null||a.length<k||k<1)

return

null; Deque<Integer>deck=newArrayDeque<>(k);//预先知道队列的大小，选用ArrayQueue，否则LinkedList

//保证队头是滑动窗口中的最大值

for(int

i=0;i<k;i++){

while(!deck.isEmpty()&&a[i]>(a[deck.peekLast()])){

deck.pollLast(); }

deck.addLast(i); }

int[]result=new

int[a.length-k+1];

int

index=0;

result[index++]=a[deck.peekFirst()];

for(int

i=k;i<a.length;i++){

if(i-deck.peekFirst()>k-1)//超过了当前滑动窗口的最左边的位置

deck.pollFirst();

while(!deck.isEmpty()&&a[i]>(a[deck.peekLast()])){

deck.pollLast(); }

deck.addLast(i);

result[index++]=a[deck.peekFirst()]; }

return

result; }基本数据类型int，使用了比较运算符>比较大小课后练习

//适用于泛型

@SuppressWarnings("unchecked")

public

static<E>E[]slideWindowMax(E[]a,int

k){

if(a==null||a.length<k||k<1)

return

null; Deque<Integer>deck=newArrayDeque<>(k);

//保证队头是滑动窗口中的最大值

for(int

i=0;i<k;i++){ Comparable<?superE>tmp=(Comparable<?superE>)a[i];

while(!deck.isEmpty()&&tmp.compareTo(a[deck.peekLast()])>0){

deck.pollLast(); }

deck.addLast(i); } E[]result=(E[])Array.newInstance(a.getClass().getComponentType(),a.length-k+1);

int

index=0;

result[index++]=a[deck.peekFirst()];

for(int

i=k;i<a.length;i++){

if(i-deck.peekFirst()>k-1)

deck.pollFirst(); Comparable<?superE>tmp=(Comparable<?superE>)a[i];

while(!deck.isEmpty()&&tmp.compareTo(a[deck.peekLast()])>0){

deck.pollLast(); }

deck.addLast(i);

result[index++]=a[deck.peekFirst()]; }

return

result; }引用类型使用compareTo比较大小，要求该类型实现了Compable接口课后练习

//这种写法，去除了重复的代码，但for循环中多了1个if语句(执行时间会多一点)，

@SuppressWarnings("unchecked")

public

static<E>E[]slideWindowMax1(E[]a,int

k){

if(a==null||a.length<k||k<1)

return

null; Deque<Integer>deck=newArrayDeque<>(k); E[]result=(E[])Array.newInstance(a.getClass().getComponentType(),a.length-k+1);

int

index=0;

for(int

i=0;i<a.length;i++){ Comparable<?superE>tmp=(Comparable<?superE>)a[i];

while(!deck.isEmpty()&&tmp.compareTo(a[deck.peekLast()])>0){

deck.pollLast(); }

deck.addLast(i);

if(i-deck.peekFirst()>k-1)//