题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度的时候，返回空

示例1

输入
[2,3,4,2,6,2,5,1],3
返回值
[4,4,6,6,6,5]

思路

1.使用大顶堆保存数据。同时保持两个指针in和out，out指向即将离开窗口的位置，in指向即将进入窗口的位置。
2.流程：首先，每当窗口就位后，从大顶堆中取出堆顶元素放入结果列表中；然后比较堆顶元素和out指向元素的大小，如果相等，就将堆顶元素pop掉，不相等就不pop；接着将in指向的元素入队；最后out++，in++；
3.上述流程是从最小栈那题借鉴来的。和现有的使用堆删除语句的题解比较，本题解虽然空间开销大（堆会保存已遍历过的所有小等于目前窗口中最大值的值），但是时间开销小，主要是避免了remove带来的开销。

code

import java.util.*;
public class Solution {
    PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer o1,Integer o2){
            return o2.compareTo(o1);
        }
    });
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if(num==null || num.length==0 || size>num.length || size<=0) return res;
        for(int i=0;i<size;i++) pq.add(num[i]);
        int pointer_out = 0,pointer_in = size;
        while(pointer_in <= num.length){
            res.add(pq.peek());
            if(pq.peek()==num[pointer_out++]) pq.poll();
            if(pointer_in < num.length) pq.add(num[pointer_in]);
            pointer_in++;
        }

        return res;
    }
}