题解 | #滑动窗口的最大值#

import java.util.*;

public class Solution {
    /**
     * 本题的解题思路很值得学习
     * 简单的方法就是每个滑动窗口我们都遍历一遍来寻找最大值
     * 可是这样子的时间复杂度就为 O(len*size) 时间复杂度太高了,因此我们就只能能改进方法
     * 改进后的方法:因为我们只需要知道每个滑动窗口中的最大值,因此同一个滑动窗口中的比最大值
     * 小的值均没有意义,即我们不需要他们,因此我们这里通过一个双端队列(看答案学的,这里的
     * 思想很重要)来维护,双端队列中存的是元素对应在 num 数组中的下标(这个思想也很重要,
     * 存下标正好方便我们判断当前元素是否还在滑动窗口内,若存入值,就不好判断),具体的维护
     * 方法就是每次我们滑动窗口变化的时候,先判断队列头部元素是否在当前窗口内,不在就 poll
     * 掉,之后我们在新元素入队列时要"挤"掉前面小于它的数(这些数就属于小于最大值的数,我们不
     * 需要他们),这样子队列头就一直是当前滑动窗口中的最大值.之后每组就遵守相同的规则,同时将
     * 队列头部元素入 res 即可.
     * 改进后的时间复杂度:O(len)
     * @param num
     * @param size
     * @return
     */
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        //排除不合法的条件
        if (size <= 0 || size > num.length) {
            return res;
        }
        //辅助双端队列 (其中存入的是下标)
        Deque<Integer> deque = new ArrayDeque<>();
        //先将前 size 个元素入双端队列,且每个元素进入的时候都"挤"掉前面小于它的数
        for (int i = 0; i < size; i++) {
            while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        //先将这一组的最大值放入 res 中
        res.add(num[deque.peekFirst()]);
        //处理后续
        for (int i = size; i < num.length; i++) {
            //先判断双端队列中头部元素是否当前滑动窗口内,不在就弹出
            if (deque.peekFirst() < i - size + 1) {
                deque.pollFirst();
            }
            //将当前窗口要加入的值入双端队列,规则与之前相同
            while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            //将当前滑动窗口的最大值加入 res 中
            res.add(num[deque.peekFirst()]);
        }
        return res;
    }
}