LeetCode239. 滑动窗口最大值

题目链接：LeetCode239

题解

暴力可以做，不知道能不能过，这题是一道双端队列求窗口最大值的问题，首先创建一个双端队列，在java中，LinkedList底层实现就是双向链表，用它存储最大值的数组下标。

如果队列不为空并且队列尾部的值nums[qres.peekLast()] <= nums[i]，就将尾部的值弹出，直到队列为空或者nums[qres.peekLast()] > nums[i]，此时就将这个下标值i进队

当窗口的左边界的下标i-k==qres.peekFirst()，就弹出头元素，因为此时该元素已经不在窗口内，过期了。剩下的情况就是当窗口长度完全为3之后，每次移动都获取队头元素即可

代码

class Solution {
    static LinkedList<Integer> qres = new LinkedList<Integer>();
    public static int[] maxSlidingWindow(int[] arr,int k) {
        qres.clear();
        if(arr == null || arr.length == 0)
            return new int[] {};
        int index = 0;
        int[] res = new int[arr.length - k + 1];
        for(int i = 0;i < arr.length;i++) {
            while(!qres.isEmpty() && arr[qres.peekLast()] <= arr[i])
                qres.removeLast();
            qres.addLast(i);
            if(qres.peekFirst() == i - k)
                qres.removeFirst();
            if(i >= k - 1)
                res[index++] = arr[qres.peekFirst()];
        }
        return res;
    }
}