LeetCode239—滑动窗口最大值

堆 双端队列 单调队列

第一次提交的代码：（堆）

class Solution 
{
    public int[] maxSlidingWindow(int[] nums, int k) 
    {
        int n=nums.length;
        int[] ans=new int[n-k+1];
        Queue<int[]> Q=new PriorityQueue<>((a,b)->a[0]==b[0]?b[1]-a[1]:b[0]-a[0]);//比较器写法，若->右边的数大于0，则交换。
        //原来队列可以把数组作为元素
        for(int i=0;i<k;i++) Q.offer(new int[]{nums[i],i});//在队列中插入数组的姿势
        ans[0]=Q.peek()[0];
        for(int i=k;i<n;i++)
        {
            Q.offer(new int[]{nums[i],i});
            while(Q.peek()[1]<=i-k) Q.poll();//已经不在窗口内的数不断出队即可。
            ans[i-k+1]=Q.peek()[0];
        }
        return ans;
    }
}

第二次提交的代码：（双端队列+单调队列）

class Solution 
{
    public int[] maxSlidingWindow(int[] nums, int k) 
    {
        int n=nums.length;
        int[] ans=new int[n-k+1];
        Deque<Integer> Q=new ArrayDeque<>();//Deque不是接口，ArrayDeque、LinkedList等才是
        for(int i=0;i<k;i++) 
        {
            while(!Q.isEmpty()&&nums[Q.peekLast()]<=nums[i]) Q.pollLast();//维护一个从大到小的单调队列（不过内容是数字的位置编号）
            Q.offerLast(i);
        }
        ans[0]=nums[Q.peekFirst()];
        for(int i=k;i<n;i++)
        {
            while(!Q.isEmpty()&&nums[Q.peekLast()]<=nums[i]) Q.pollLast();
            Q.offerLast(i);
            while(Q.peekFirst()<=i-k) Q.pollFirst();//出了窗口的出队
            ans[i-k+1]=nums[Q.peekFirst()];
        }
        return ans;
    }
}