LeetCode 239. 滑动窗口最大值

1、题目

image.png

2、分析

使用单调队列的方法
https://labuladong.github.io/zgnb/6/34/

3、代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotoneQueue window = new MonotoneQueue();
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(i < k - 1){
                window.push(nums[i]);
            }else{
                window.push(nums[i]);
                res.add(window.max());
                window.pop(nums[i - k + 1]);
            }
        }
        int[] ans = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
}

class MonotoneQueue{
    LinkedList<Integer> queue = new LinkedList<>();
    public void push(int x){
        while(!queue.isEmpty() && queue.getLast() < x){
            queue.removeLast();
        }
        queue.addLast(x);
    }

    public void pop(int x){
        if(queue.getFirst() == x){
            queue.removeFirst();
        }
    }

    public int max(){
        return queue.getFirst();
    }
}