随笔记录

算法-滑动窗口（滑动窗口中的最大值）

2022-5-6 diaba 算法

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;
    }
}