package com.jiucaiyuan.net.question;



import java.util.LinkedList;



/**

 * 滑动窗口结构及滑动窗口应用

 *

 * @Author jiucaiyuan  2022/5/5 23:17

 * @mail services@jiucaiyuan.net

 */



public class WindowMax {

    private int l;

    private int r;

    private int[] arr;  // arr[  [l  ..  r)     ]

    private LinkedList<Integer> qMax;  //保存数组中的下标，尾部加入数据，头部获得最大值



    public WindowMax(int[] a) {

        l = -1;

        r = 0;

        arr = a;

        qMax = new LinkedList<>();

    }



    public void addNumFromRight(int num) {

        if (r == arr.length) {

            return;

        }

        //如果双端队列不为空，刚进入窗口的数大于等于双端队列尾部的数

        while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[r]) {

            qMax.pollLast();

        }

        qMax.addLast(r);

        r++;

    }



    public void removeNumFromLeft() {

        if (l >= r - 1) {

            return;

        }

        l++;

        //如果头部是要出窗口的数字，弹出

        if (arr[qMax.peekFirst()] == l) {

            qMax.pollFirst();

        }

    }



    /**

     * 获取窗口内最大值

     * 双端队列头到尾，单调递减

     *

     * @return

     */

    public Integer getMax() {

        if (!qMax.isEmpty()) {

            return arr[qMax.peekFirst()];

        }

        return null;

    }



    //以上是滑动窗口的结构介绍

    //以下是本体的解题代码



    /**

     * <pre>

     * 【题目】

     * 有一个整形数组arr和一个大小为w的窗口，窗口从最左边滑到最右边，

     * 窗口每次向右滑动一个位置。

     * 例如：数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：

     *  [4,3,5,]4,3,3,6,7

     *  4,[3,5,4,]3,3,6,7

     *  4,3,[5,4,3,]3,6,7

     *  4,3,5,[4,3,3,]6,7

     *  4,3,5,4,[3,3,6,]7

     *  4,3,5,4,3,[3,6,7]

     *  窗口中最大值为5 5 5 4 6 7

     *  如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口最大值

     *  请实现一个函数，输入整形数组arr，和窗口大小w，输出一个长度为n-w+1的数组res，

     *  res[i]表示每个窗口状态下的最大值，

     *  本例输出[5,5,5,4,6,7]

     *  </pre>

     *

     * @param arr 待扫描的数组

     * @param w   窗口大小

     * @return 滑动过程中形成窗口中的最大值

     */

    public static int[] getMaxWindow(int[] arr, int w) {

        if (arr == null || w < 1 || arr.length < w) {

            return null;

        }

        //双端队列，存储下标，值从大到小的顺序

        LinkedList<Integer> qmax = new LinkedList<>();

        int[] res = new int[arr.length - w + 1];

        int index = 0;

        for (int i = 0; i < arr.length; i++) {

            //当前入队时，要保证双端队列是单调递减的，从尾部加入，如果尾部元素<=当前值，出队

            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {

                qmax.pollLast();

            }

            qmax.addLast(i);

            if (qmax.peekFirst() == i - w) {  // i-w 是过期的下标

                qmax.pollFirst();

            }

            if (i >= w - 1) { //形成窗口了

                res[index++] = arr[qmax.peekFirst()];

            }

        }

        return res;

    }

}