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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @param size int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        // write code here
        // 核心思想：设置一个【单调双端队列】，确保队头是当前窗口内的最大值

        // 0.判断特殊情况
        ArrayList<Integer> result = new ArrayList<>();
        if (size <= 0 || size > num.length) {
            return result;
        }

        // 1.创建双端队列
        Deque<Integer> dq = new LinkedList<>();

        // 2.录入初始窗口
        int h = 0;
        int t = size - 1;
        for (int i = h; i <= t; i++) {
            // 录入的是下标
            inDequeue(num, i, dq);
        }

        // 3.得到初始窗口的结果
        // 注意！从队列中取出来的是下标值，要转换成元素值存入结果中
        result.add(num[dq.peekFirst()]);

        // 4.模拟窗口移动-h右移且t右移，不断得到结果
        for (int i = 1; i <= (num.length - size); i++) {
            // 4.1 t后移，新元素入队
            inDequeue(num, ++t, dq);
            // 4.2 h后移，旧元素出队
            outDequeue(num, h++, dq);
            // 4.3 新窗口形成，从队头获得当前窗口最大元素
            // 注意！从队列中取出来的是下标值，要转换成元素值存入结果中
            result.add(num[dq.peekFirst()]);
        }

        return result;
    }

    // 新元素入单调双端队列的操作
    public void inDequeue(int[] num, int i, Deque<Integer> dq) {
        // 录入的是下标
        if (dq.isEmpty()) {
            // 若队列为空，则直接录入
            dq.addLast(i);
        }
        else if (num[i] < num[dq.peekLast()]) {
            // 若待录入元素小于队尾元素，则入队
            dq.addLast(i);
        } else {
            // 若待录入元素大于等于队尾元素，则不断地让堆尾元素出队，直到满足小于队尾元素入队
            // 等于也要出队的目的是让新的元素替代队列中旧的元素
            while (!dq.isEmpty() && num[i] >= num[dq.peekLast()]) {
                dq.pollLast();
            }
            // 此时队列空了，或者队尾下标元素大于当前待入队元素
            dq.addLast(i);
        }
    }

    // 旧元素出单调双端队列的操作
    public void outDequeue(int[] num, int i, Deque<Integer> dq) {
        // 录入的是下标
        if (i == dq.peekFirst()) {
            // 当待出队元素正好是队头元素（当前窗口最大）时才出队
            dq.pollFirst();
        }
        // 当待出队元素不是队头元素（当前窗口最大）时不用出队
    }
}