class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        mydeque deque=new mydeque();
        int n=nums.length;
        int[] res=new int[n-k+1];
        for(int i=0;i<n;i++){
            if(i<k-1){
                deque.push(nums[i]);
            }else{
                deque.push(nums[i]);
               res[i-k+1]=deque.getmax();
                deque.pop(nums[i-k+1]);
            }
        }
        return res;
    }

}

class mydeque{
    LinkedList<Integer> list=new LinkedList<>();
    void push(int val){
        while(!list.isEmpty()&&list.getLast()<val){
            list.removeLast();
        }
        list.addLast(val);
    }

    void pop(int n){
        if(n==list.getFirst()) list.removeFirst();
    }

   int getmax(){
       return list.getFirst();

    }
}