题解 | #滑动窗口的最大值#

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        Deque<Integer>deque=new LinkedList<>();
        int arrlength=num.length-size+1;
        ArrayList<Integer>a=new ArrayList<>(arrlength);
        Integer[]temp=new Integer[size];
        int []temp2=new int [size];
        
        //当前窗口最小值
        int max=-999999;
        //前size个元素先入队尾
        for(int i=0;i<size;i++){
            deque.offerLast(num[i]);
            if(num[i]>max)
                max=num[i];
        }
        a.add(max);
        System.out.println(arrlength);
        //针对窗口数的循环
        for(int i=1;i<arrlength;i++){
            //扫描流程
            //每到一个元素将该元素加入到队尾，并比较它和min的大小，
            //如果小就修改min，并加入结果ArrayList；
            //然后将第一个元素出队，并比较它与min是否相同：
            //不同，该元素非最小元素，继续执行
            //相同，需要重新对deque进行排序，这里采用快排序
            deque.offerLast(num[size-1+i]);
            if(num[size-1+i]>max){
                max=num[size-1+i];
                a.add(max);
                deque.pollFirst();
            }else{
                int f=deque.pollFirst();
                if(f==max){
                    deque.toArray(temp);
                    for(int j=0;j<size;j++)
                        temp2[j]=temp[j];
                    quicksort(temp2,0,size-1);
                    max=temp2[size-1];
                }
                a.add(max);
            }
            

        }
        return a;
    }
    public void quicksort(int []a,int s,int e){

        if(s>=e)return ;
        int pivot=(int)(s+Math.random()*(e-s+1));
        int temp=a[s];
        a[s]=a[pivot];
        a[pivot]=temp;
        int base=a[s];
        int l=s,h=e;
        while(l<h){
            while(l<h&&a[h]>=base)
                h--;
            a[l]=a[h];
            while(l<h&&a[l]<=base)
                l++;
            a[h]=a[l];
        }
        a[l]=base;
        if(l==a.length-1)
            return ;
        else 
            quicksort(a,l+1,e);   
    }
}