239. 滑动窗口最大值(leetcode)

https://leetcode.cn/problems/sliding-window-maximum/

简单的滑动窗口,但是与ACM模式的维护数组不同,在leetcode定义单调队列类更加方便

class MyQueue{
    // 单调队列实现,递减
    Deque<Integer> deque = new LinkedList<>();
    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }

    void add(int val){
        while(!deque.isEmpty() && deque.getLast() < val){
            deque.removeLast();
        }
        deque.add(val);
    }

    int peek(){
        return deque.peek();
    }
}



class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n-k+1];
        int len=0;
        MyQueue q = new MyQueue();
        for(int i=0;i<k;i++)q.add(nums[i]);
        res[len++]=q.peek();
        for (int i = k; i < nums.length; i++) {
            // 移除队尾,若该元素仍在队列中则移除
            q.poll(nums[i - k]);
            // 加入队列,移除队列中比该元素小的,保持单调
            q.add(nums[i]);
            res[len++] = q.peek();
        }
        return res;
    }
}