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

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
        Deque q = new ArrayDeque<int[]>();

        if (size == 0 || size > num.length)return new ArrayList<Integer>();
        int m = Integer.MIN_VALUE;


        for (int i = 0; i < size; i++) {     //前面size个单独处理
            m = Math.max(m, num[i]);
            while (q.size() > 0) {
                int[] fr = (int[]) q.peekLast();
                int fid = fr[1], fx = fr[0];
                if (num[i] >= fx)q.pollLast();
                else break;
            }
            q.addLast(new int[] {num[i], i});
        }
        int n = num.length;

        int []ans = new int[n - size + 1];
        ans[0] = m;

        for (int j = size; j < n; j++) {//遍历每一个元素
            int x = num[j];

            if (q.size() > 0) {           //根据下标判断是否还有用
                int[] fr = (int[]) q.peekFirst();
                int fid = fr[1];
                if (fid <= j - size)q.pollFirst();
            }
            while (q.size() > 0) {      //根据大小，如果右边有个比自己大的进来，自己就没用了，单调递减栈
                int[] fr = (int[]) q.peekLast();
                int fid = fr[1], fx = fr[0];
                System.out.println(x + ":" + fx);
                if (x >= fx)q.pollLast();
                else break;
            }

            if (q.size() > 0) {          //如果还有元素，那么最大值就是数组最大
                int[] fr = (int[]) q.peekFirst();
                int fx = fr[0];
                ans[j - size + 1] = fx;
            } else ans[j - size + 1] = num[j];
            q.addLast(new int[] {num[j], j});//如果没有元素，那么最大值就是自己
        }

        ArrayList<Integer>res = new ArrayList<Integer>();
        for (int i : ans)res.add(i);

        return res;
    }
}