Leetcode--239. 滑动窗口最大值

题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

运行结果

思路总结
之前牛客上是采用双指针加大顶堆实现的。但是会出现超时，无法通过
题解的思路是采用双端队列的方式（思想和实现一个求最大值的队列的时间为O（1）是一样的）
1.维持一个单调序列：即维持一个序列满足单调。（队列里存的是一个滑动窗口的情况）
入队规则：如果要加入的元素比队尾元素大，则移除队尾元素，直到小于队尾元素时，将该元素入队
出队规则：队头一直是当前队列的最大值。---当窗口右移时，如果窗口前移出的值和队头元素一致，则移除队头
最后滑动窗口的最大值一定是队头元素，直接入队即可

import java.util.*;
class Solution {
    //双指针加大顶堆---超时
    /*public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans=new int[nums.length-k+1];
        if(k <=0 || k > nums.length) return ans;
        PriorityQueue<Integer> max_heap=new PriorityQueue<Integer>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o2-o1;
            }
        }); 
        for(int i=0,j=k;j<=nums.length;i++,j++){
            for(int m=i;m<j;m++){
                max_heap.offer(nums[m]);
            }
            ans[i]=max_heap.peek();
            max_heap.clear();
        }
        return ans;
    }*/
    //求最大值时间为O（1）的队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) {
            return nums;
        }
        int[] ans = new int[len - k + 1];
        int ans_index = 0;
        //我们需要维护一个单调递增的双向队列
        Deque<Integer> deque = new LinkedList<>();
        //先将第一个窗口的值按照规则入队
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
               deque.removeLast();
            }
            deque.offerLast(nums[i]);
        }
        //存到数组里，队头元素
        ans[ans_index++] = deque.peekFirst();
        //移动窗口
        for (int j = k; j < len; j++) {
            //对应咱们的红色情况，则是窗口的前一个元素等于队头元素
            if (nums[j - k] == deque.peekFirst()) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < nums[j]) {
                deque.removeLast();
            }
            deque.offerLast(nums[j]);
            ans[ans_index++] = deque.peekFirst();
        }
        return ans;
    }
}