窗口内最大值或最小值的更新结构——窗口内最大值

题目

假设一个固定大小为W的窗口，依次划过arr，返回每一次滑出状况的最大值
例如，arr= [4,3,5,4,3,3,6,7]， W= 3。返回：[5,5,5,4,6,7]。

双端队列含义：窗口依次缩小的情况下，哪些位置的数会依次成为窗口内的最大值

package com.harrison.class13;

import java.util.LinkedList;

/** * @author Harrison * @create 2022-03-25-13:07 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。 */
public class Code01_SlidingWindowMaxArray {
    
    public static int[] right(int[] arr, int w) {
    
        if (arr == null || arr.length < w || w < 1) {
    
            return null;
        }
        int N = arr.length;
        int[] res = new int[N - w + 1];
        int L = 0;
        int R = w - 1;
        int index = 0;
        while (R < N) {
    
            int max = arr[L];
            for (int i = L + 1; i <= R; i++) {
    
                max = Math.max(max, arr[i]);
            }
            res[index++] = max;
            L++;
            R++;
        }
        return res;
    }

    public static int[] getMaxWindow(int[] arr, int w) {
    
        if (arr == null || arr.length < w || w < 1) {
    
            return null;
        }
        int N = arr.length;
        int[] res = new int[N - w + 1];
        int index = 0;
        // 放下标
        LinkedList<Integer> qmax = new LinkedList<>();
        for (int R = 0; R < N; R++) {
    
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
    
                qmax.pollLast();
            }
            qmax.addLast(R);
            // R-w：窗口过期下标
            if (qmax.peekFirst() == R - w) {
    
                qmax.pollFirst();
            }
            // 是否形成一个正常的窗口
            if (R >= w - 1) {
    
                res[index++]=arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
    
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
    
            arr[i] = (int) (Math.random() * (maxValue + 1));
        }
        return arr;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
    
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
    
            return false;
        }
        if (arr1 == null && arr2 == null) {
    
            return true;
        }
        if (arr1.length != arr2.length) {
    
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
    
            if (arr1[i] != arr2[i]) {
    
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
    
        int testTime = 100000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
    
            int[] arr = generateRandomArray(maxSize, maxValue);
            int w = (int) (Math.random() * (arr.length + 1));
            int[] ans1 = getMaxWindow(arr, w);
            int[] ans2 = right(arr, w);
            if (!isEqual(ans1, ans2)) {
    
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }
}