《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 5-4雙端隊列的一個例子

課后練習(xí)//生成滑動窗口的最大值數(shù)組//例如，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]//結(jié)果：//5,5,5,4,6,7課后練習(xí)

public

static

int[]slideWindowMax(int[]a,int

k){

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

return

null; Deque<Integer>deck=newArrayDeque<>(k);//預(yù)先知道隊列的大小，選用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)//超過了當(dāng)前滑動窗口的最左邊的位置

deck.pollFirst();

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

deck.pollLast(); }

deck.addLast(i);

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

return

result; }基本數(shù)據(jù)類型int，使用了比較運(yùn)算符>比較大小課后練習(xí)

//適用于泛型

@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比較大小，要求該類型實現(xiàn)了Compable接口課后練習(xí)

//這種寫法，去除了重復(fù)的代碼，但for循環(huán)中多了1個if語句(執(zhí)行時間會多一點(diǎn))，

@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)//