【 Data structure and algorithm 】 sliding window details

The sliding window

1. The window

A window is a particular kind of trajectory.

As shown in the figure above, the left and right bounds of the window start at the far left of the array, leaving the window empty.

The window’s left boundary L and right boundary R can only move to the right, not the left. At the same time, one principle must be followed when moving: the left boundary L must not move to the right of the right boundary R (L must not go beyond R).

L and R can always move to the right as long as they don’t violate the rules.

When R moves to the right, one element of the array enters the window from the right side of the window.

When L moves to the right, one element in the array exits the window on the left side.

If we encapsulate L move right and R move right into two interfaces that developers can call. In this way, each call will form a different window state.

If we need to get the maximum value for the current window state, we usually iterate through the entire window, which is not cheap enough. Is there a structure that can be used to get the maximum or minimum value of the current window state at a very low cost?

This is the window maximum or minimum update structure.

2. The introduction of

The structure is introduced by a topic.

Topic:

There is an integer array arr and a window of size W that slides from the left to the right of the array, one position at a time.

For example, if arr is {4,3,5,4,3,3,6,7} and the sliding window size is 3:

[4 3 5] 4 3 3 6 7 Maximum window = 5

4 [3 5 4] 3 3 6 7 Maximum window = 5

4 3 [5 4 3] 3 6 7 Maximum window = 5

4 3 5 [4 3 3] 6 7 Maximum window = 4

4 3 5 4 [3 3 6] 7 Maximum window = 6

4 3 5 4 3 [3 6 7] Window maximum = 7

If the array length is N and the window size is W, a total of N – W +1 Windows will be generated.

Implement a function that collects the maximum value for each window state.

Input: integer array arr, window size W

Output: an integer array of length n-w+1 that records the maximum value for each window state, as above [5,5,5,4,6,7].

3. Maximum update structure

Gets the structure of the maximum value in the window in any window state.

Build a double-endian queue, where you can get in and out of a node from the head as well as from the tail.

A double-ended queue stores the indices of the elements in the array. Why not store elements? Because subscripts can not only represent elements, but also indicate their position in the array, which carries more information.

If the maximum update structure is used, then the monotonicity is from large to small, that is, the element corresponding to the subscript stored from beginning to end of the two-ended queue is from large to small.

R moves one bit to the right:

If the double-endian queue is empty, then the index of the element newly included by R enters the double-endian queue directly from the tail.
If the double-endian queue is not empty, then the element newly included by R needs to be compared with the element pointed to by the subscript at the end of the double-endian column:
- If the newly included element is smaller than the element indicated by the subscript at the end of the double-endian column, it enters the double-endian column directly from the tail.
- If the newly included element is larger or equal to the element pointed to by the trailing subscript of the double-enantied column, the trailing subscript is ejected from the tail of the double-enantied queue so that the newly included element continues to be compared to the element pointed to by the current trailing subscript.

As long as the subscript that pops up from the end of the two-ended queue is never retrieved.

The maximum value of a double-ended queue at any time is the element stored in the header or the value represented by the element.

By designing this rule, you are strictly maintaining the monotony of a two-ended queue.

L Move one bit to the right:

We just need to compare the subscript corresponding to the newly expelled element of L with the subscript corresponding to the header of the double-ended queue:
- If the index of the newly expelled element is the same as the index of the header of the two-ended queue, the header is ejected from the header.
- If the index of the newly expelled element is different from that of the header of the double-endian queue, no action is required.

This matches the subscript, not the element value of the subscript.

4. Minimum update structure

The minimum update structure is the same as the maximum update structure.

You just need to modify the monotonicity to make sure that the subscripts of the two-ended queue stored from head to head correspond to smaller and larger elements.

Principle 5.

Why is the maximum value of each window state the value of the current two-ended queue header?

So we need to figure out what information is being maintained in a two-ended queue.

It maintains the information that if you don’t let R move to the right and you let L move to the right, who in turn becomes the maximum.

Suppose you now have an array arr = {6,5,4,3, 5, 7} and the window area is [6,5,4,3].

At this point, the maximum value maintained by the dual-end queue is ARR [0] = 6.

If R is left standing and L moves one bit to the right, arr[0] expires and arr[1] becomes the maximum. If L moves one more bit to the right, arr[1] also expires and arr[2] becomes the maximum. And so on.

If L is left still and R moves one bit to the right, then 3, 2, and 1 all pop up in turn, and then 4 comes in.

3, 2 and 1 pop up because ARR [4] = ARR [1] > ARR [2] > ARR [3], and ARR [1], ARR [2] and ARR [3] must expire earlier than ARR [4]. So ARR [1], ARR [2], and ARR [3] no longer have a chance to be the maximum, so it is enough to pop straight out of the two-ended queue and let ARR [4] push into the two-ended queue.

Therefore, it can also be said that a double-endian queue maintains information about who will become the maximum in turn if it expires in turn.

6. Time complexity

As the window slides right through the array, count the number of times each element moves in and out of the window.

Each element can enter the window at most once and leave the window at most once. An element that has already left the window does not return to the window, so there is no such thing as an element entering the window more than once.

So when the window slides to the right of N elements, the total cost of the double-ended queue update must be O(N), the cost of a single update is O(N)/N, so the average cost of a single update is O(1).

Note that just because the average cost is O(1) does not mean that every update is O(1).

For example, if arr = {6,5,4,3,2,1, 7} and the window is [6,5,4,3,2,1], L moves and R moves one bit to the right, then the cost of updating the double-ended queue is O(N). However, the update cost of entering the window double-end queue at positions 0~5 is O(1). It can be said that at a certain moment, the complexity of updating a single element may be relatively high, but the total cost is very low on average.

7. The problem solving