// @Title: 望远镜中最高的海拔 (望远镜中最高的海拔)
// @Author: qisiii
// @Date: 2022-03-04 14:37:47
// @Runtime: 14 ms
// @Memory: 50.6 MB
// @comment: 使用双向队列
// @flag: BLUE
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length<1||k<=0){
            return new int[0];
        }
        Deque<Integer> deque=new LinkedList();
        int[] result=new int[nums.length-k+1];
        int index=0;
        //先获取第一个窗口的最大值队列
        for (int i = 0; i < k; i++) {
            //当新值大于队尾的时候，弹出队尾
            while(!deque.isEmpty()&&nums[i]>nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offer(i);
        }
        result[index]=nums[deque.peekFirst()];
        for (int i = k; i < nums.length; i++) {
            //当队首不在窗口内时，出队
            if(deque.peekFirst()<=i-k){
                deque.pollFirst();
            }
            //当新值大于队尾的时候，弹出队尾
            while (!deque.isEmpty()&&nums[i]>nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offer(i);
            result[++index]=nums[deque.peekFirst()];
        }
        return result;
    }
}