“This is the second day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

What is a sliding window?

A SlidingWindow is an imaginary data structure with a left bound L and a right bound R. On an array or a string or a sequence, call it S, the window is S[L..R], L to the right means a sample goes out of the window, R to the right means a sample goes in the window, L and R can only slide right.

What can sliding Windows do?

Whether the window L or R slides, the window will present a new state, how to get the maximum and minimum value of the current state of the window faster? The best thing to do is average it out to order 1.

Take advantage of monotonic two-ended queues! If you don’t know what a two-endian queue is, please refer to this article.

Three, sliding window implementation ideas

Four, sliding window topic

The sliding window achieves the maximum value within the window

For example, arr = [4,3,5,4,3,3,6,7], W = 3 returns: [5,5,5,4,6,7]Copy the code

Violence to achieve

public static int[] right(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
        return null;
    }
    int N = arr.length;
    int L = 0;
    int R = w - 1;
    int[] ans = new int[N - 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]);
        }
        ans[index++] = max;
        R++;
        L++;
    }
    return ans;
}
Copy the code

Use sliding Windows to achieve

// Make use of sliding window, double-end queue
public static int[] getMaxWindow(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
        return null;
    }
    LinkedList<Integer> queueMax = new LinkedList<>();
    int[] res = new int[arr.length - w + 1];
    int index = 0;
    for (int R = 0; R < arr.length; R++) {
        while(! queueMax.isEmpty() && arr[queueMax.peekLast()] <= arr[R]) { queueMax.pollLast(); } queueMax.addLast(R);// Window expiration subscript
        if (queueMax.peekFirst() == R - w) {
            queueMax.pollFirst();
        }
        // The window is preheated and answers are collected when the window size is reached
        // Whether the normal window is formed now, if the window is not formed, the window belongs to the cultivation period, there is no need to collect answers
        if (R >= w - 1) { res[index++] = arr[queueMax.peekFirst()]; }}return res;
}
Copy the code

test

public static void main(String[] args) {
    int[] arr = {4.3.5.4.3.3.6.7};
    int w = 3;
    System.out.println(Arrays.toString(right(arr, w)));
    System.out.println(Arrays.toString(getMaxWindow(arr, w)));
}
Copy the code