单调队列解决滑动窗口问题

力扣链接：剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣（LeetCode） (leetcode-cn.com)

剑指 Offer 59 - II. 队列的最大值 - 力扣（LeetCode） (leetcode-cn.com)

单调队列

队列中的元素呈现一定的单调性，单调递增或单调递减

滑动窗口问题

指求解在指定范围内的最值问题，并且这个范围还会移动或改变

滑动窗口的最大值

滑动窗口的最大值：剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣（LeetCode） (leetcode-cn.com)

思路

• 构造一个单调递减的队列
• 获取当前队列的首元素即可获取当前窗口的最大值
• 当单调队列中的最大值在滑动窗口范围外，就弹出队首元素
• 当新增元素大于等于队尾元素时，就不断弹出队尾元素，直到队尾元素大于新增元素，再新增元素

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || nums.length<k){
            return new int[0];
        }
        // 单调递减队列，记录元素下标
        Deque<Integer> deque = new LinkedList<>();
        // 记录每个窗口的最大值
        List<Integer> res = new ArrayList<>();
        // 遍历所有元素
        for (int i = 0; i < nums.length; i++) {
            // 单调队列不为空并且队首元素不在窗口范围内时就弹出队首元素
            if (!deque.isEmpty() && i-deque.peek()>=k){
                deque.remove();
            }
            // 单调队列不为空并且新增元素大于等于队尾元素就不断弹出队尾元素
            while(!deque.isEmpty() && nums[i]>=nums[deque.peekLast()]){
                deque.removeLast();
            }
            // 新增元素
            deque.add(i);
            // 形成相应大小的滑动窗口范围时记录单调队列的队首元素
            if (i>=k-1){
                res.add(nums[deque.peek()]);
            }
        }
        // 返回结果
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

队列的最大值

剑指 Offer 59 - II. 队列的最大值 - 力扣（LeetCode） (leetcode-cn.com)

思路

一个队列用于记录元素，一个单调队列用于记录队列中的最值

代码

class MaxQueue {
    // 队列
    Queue<Integer> queue = null;
    // 单调递减队列
    Deque<Integer> deque = null;
    // 构造函数
    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }

    // 获取最大值
    public int max_value() {
        // 如果单调队列为空
        if (deque.isEmpty()){
            return -1;
        }
        // 返回单调队列队首元素
        return deque.peek();
    }

    // 存放元素
    public void push_back(int value) {
        // 在队列中添加元素
        queue.add(value);
        // 在单调递减队列中弹出小于等于新增元素的队尾元素
        while (!deque.isEmpty() && deque.peekLast()<=value){
            deque.pollLast();
        }
        // 在单调队列队尾添加元素
        deque.addLast(value);
    }

    // 弹出元素
    public int pop_front() {
        // 如果队列为空
        if (queue.isEmpty()){
            return -1;
        }
        // 如果队列队首元素等于单调队列队首元素
        if (queue.peek().equals(deque.peekFirst())){
            // 弹出单调队列队首元素
            deque.pollFirst();
        }
        // 返回队列队首元素
        return queue.poll();
    }
}