AcWing 79. 比单调队列更快的做法Java    原题链接    困难

作者： 作者的头像   还想听你的故事 ,  2020-07-23 17:23:56 ,  所有人可见 ,  阅读 511

0 


class Solution {
    public int[] maxInWindows(int[] nums, int k) {
        if(nums.length==3) return nums;
            List<Integer>list=new ArrayList<>();
            int max=Integer.MIN_VALUE;
            int pos=-1;
            for(int i=0;i<k;i++){
                if(nums[i]>max) {
                    max=nums[i];
                    pos=i;
                }
            }
            list.add(max);
            for(int i=k;i<nums.length;i++){
                int j=i-k+1;
                if(j<=pos){
                    if(nums[i]>max){
                        max=nums[i];
                        pos=i;
                    }
                }else{
                    max=Integer.MIN_VALUE;
                    for(int m=i-k+1;m<=i;m++){
                        if(nums[m]>max){
                            max=nums[m];
                            pos=m;
                        }
                    }
                }
                list.add(max);
            }
            int res[]=new int[list.size()];
            int index=0;
            for(int num:list) res[index++]=num;
            return res;

    }
}

1 评论

用户头像
还想听你的故事   2020-07-23 17:27         踩      回复

单调队列

class Solution {
    public int[] maxInWindows(int[] nums, int k) {
            int n=nums.length;
            if(n==3) return nums;
            int res[]=new int[n-k+1];
            Deque<Integer>queue=new LinkedList<>();
            for(int i=0;i<n;i++){
                while(!queue.isEmpty()&&nums[i]>=nums[queue.peekLast()]) queue.removeLast();
                queue.add(i);
                if(i-k+1>queue.getFirst()) queue.removeFirst();
                if(i-k+1>=0) res[i-k+1]=nums[queue.getFirst()];
            }
            return res;
    }
}