滑动窗口的最大值 四种解法

题目：

给定一个数组和滑动窗口的大小，找出每个​滑动窗口中的最大值。数组大小为n，滑动窗口大小为k（0<k<=n）

思路：

思路一​：

两重循环。实现虽然很简单，但是时间复杂度较高。O(nk)

思路​二：

利用堆排的思路维护一个最大堆，​同时清理过期元素。时间复杂度为O（nlogk）

思路​三：

通过预处理保存​一个固定范围的最大值​。利用一个较简单的预处理，可以求出每个元素开始的2，4，8。。。直到窗口大小/2 个元素的最大值，这样再进行遍历的时候可以将窗口分成两部分，​两部分中的较大值就是当前滑动窗口的最大值。

​思路四：

维护一个单调队列，在新元素入队时，从队列头删除所有值小于新元素的元素，​元素过期时从队尾移除。队尾的元素就是滑动窗口的最大值。

代码：

public class Solution {

    public ArrayList<Integer> maxInWindows(int [] num, int size)

    {

        ArrayList<Integer> ans = new ArrayList<>();

        if (size == 0) return ans;

        MyQueue q = new MyQueue(size,num);

        for (int i = 0;i<size-1;i++){

            q.add(i);

        }

        for (int i = size-1;i<num.length;i++){

            q.add(i);

            ans.add(q.get());

        }

        return ans;

    }

    class MyQueue{

        int size;

        LinkedList<Integer> queue;

        int[] num;

        MyQueue(int size,int[] num){

            this.size = size;

            this.num = num;

            queue = new LinkedList<>();

        }

        void add(int k){

            while (queue.size()>0&&num[queue.getFirst()]<=num[k]){

                queue.pollFirst();

            }

            queue.addFirst(k);

            while(queue.getLast()+size-1<k){

                queue.pollLast();

            }

        }

        int get(){

            return num[queue.getLast()];

        }

    }

}