239. Sliding Window Maximum!

Sliding window: monotonic queue

// a data structure that mananges elements in descending order
class MonoQueue{
    private LinkedList<Integer> descList = new LinkedList<>();
    public int max(){
        return descList.getFirst();
    }
    
    public void push(int num){
        // remove all the elements that are smaller than num
        while(descList.size()>0 && descList.getLast()<num){
            descList.removeLast();
        }
        descList.addLast(num);
    }
    // remove the element that move out of window
    public void removeMax(){
        // max element is the first element
        descList.removeFirst();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length-k+1];
        MonoQueue monoQueue = new MonoQueue();
        for(int i=0; i<nums.length; i++){
            // keep adding num to monoQueue
            if(i<k-1){
                monoQueue.push(nums[i]);
            }else{
                monoQueue.push(nums[i]);
                result[i-k+1] = monoQueue.max();
                // if the max value is the last element of the window,
                // remove the value;
                if(nums[i-k+1]==monoQueue.max()){
                    monoQueue.removeMax();
                }
            }
        }
        return result;
    }
}