LeetCode239. 滑动窗口最大值

暴力解法会时间超时。所以就只能用单调队列来解决了。

首先用数组来实现单调队列，定义一个数组，用来实现单调队列里面存放下标，head指向队列的头节点（且当前头结点在滑动窗口内），tail指向队列的尾结点。

当队列要加入一个元素时，因为本题是单调递增的，所以在加入一个元素时，如果当前元素比队列尾部元素小，就直接加入；如果比尾部元素大，就把队列里所有比当前元素小的元素删除，然后将当前元素加入队列即可。

当队列头指针指向的元素已经不在当前窗口内里就是窗口向后移动了，head也向后移动一位。

只要滑动窗口的大小为3时，就将队列中头元素的值加入到结果集中。

暴力代码：超时

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int index = 0;
        int max  = nums[0];
        int[] res = new int[nums.length-k+1];
        int index2 = 0;
        for(int i = 0;i=max){
                    max = nums[index];
                }
                index++;
            }
            res[index2++] = max;
        }
        return res;
    }
}

用单调队列（数组）来实现：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int index = 0;
        int head = 0;
        int tail = -1;
        int[] moQue = new int[nums.length];
        int[] res = new int[nums.length-k+1];
        for (int i = 0; i < nums.length; ++ i) {
            // 判断队头是否已经滑出窗口
            if (head <= tail && i - k + 1 > moQue[head])  ++ head;
            
            // 维护队列的单调性
            while (head <= tail && nums[i] > nums[moQue[tail]])  -- tail;
            moQue[++ tail] = i;
            
            // 输出最小值
            if (k <= i + 1) 
                res[index++] = nums[moQue[head]];
        }
        return res;
    }
}