题解 | #三数之和#

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
      //1,暴力算法运行超时
        /*
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < num.length-size+1; i++) {
            int max = num[i];
            for (int j = i; j < i+size; j++) {
                max = max<num[j]?num[j]:max;
            }
            res.add(max);
        }
        return res;
         */
        //2.双指针+双层遍历  运行超时
        /*
        ArrayList<Integer> res = new ArrayList<>();
        if(num.length<size || num == null || size<1){
            return res;
        }
        int left = 0,right = 0;
        while (left+size<=num.length){
            right = left+size-1;
            int max = Integer.MIN_VALUE;
            for (int i = left; i <= right; i++) {
                max = max>num[i]?max:num[i];
            }
            res.add(max);
            left++;
        }
        return res;
         */
        //3。最大堆求解 运行超时
        /*
        PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>((o1, o2)->o2-o1);//大顶堆
        ArrayList<Integer> result = new ArrayList<Integer>();//保存结果


            if(num==null || num.length<=0 || size<=0 || size>num.length){
                return result;
            }
            int count=0;
            for(;count<size;count++){//初始化滑动窗口
                maxQueue.offer(num[count]);
            }
            while(count<num.length){//对每次操作，找到最大值（用优先队列的大顶堆），然后向后滑动（出堆一个，入堆一个）
                result.add(maxQueue.peek());
                maxQueue.remove(num[count-size]);
                maxQueue.add(num[count]);
                count++;
            }
            result.add(maxQueue.peek());//最后一次入堆后没保存结果，这里额外做一次即可

            return result;
         */
         //4.单调队列
        ArrayList<Integer> res = new ArrayList<>();
        if(num.length<=0 || num.length<size || size<1){
            return res;
        }
        Deque<Integer> q = new LinkedList<>();
        for (int i = 0; i < num.length; i++) {
            //q中存储当前滑动窗口的值在数组中的下标
            if(q.isEmpty()){
                q.add(i);
            }else if(i-size+1>q.peekFirst()){//当q中存储窗口大小大于滑动窗口大小时，弹出队列首部的元素。
                q.pollFirst();
            }
            while (!q.isEmpty() && num[i]>=num[q.peekLast()]){//若当前队列不为空，
                // 且数组当前值大于队列中存储的最末段值，则弹出数组最末的元素
                q.pollLast();
            }
            q.add(i);
            if(i-size+1>=0){
                res.add(num[q.peekFirst()]);
            }
        }
        return res;

    }
}