Find Maximum in Sliding Window
Given an array of integers and a Window of size w, finds the current maximum value in the Window as the Window (part of the array) slides through the array.
With a Window Size of 3, let's find all the maximums as we slide.
step1 The maximum value among the three elements of Window is 2
step2 Shift by one, the maximum value among the three elements of Window is 3
step3 Shift by one, the maximum value among the three elements of Window is 6
Finally, the data structure containing 2 3 6 should be returned.
Solution
Time Complexity: O(n) All elements are pushed and popped from the deque only once in a single scan. Push and pop are O (1), so The algorithm works with Time Complexity O (n).
Space Complexity: O(w) Space Complexity is O (w) because it uses a list of Window sizes.
This algorithm uses a deque data structure to find the maximum value in the window. The purpose of using this data structure is to push and pop operations such as adding and deleting data to both ends. This is because the deque that works with O (1). This acts as a window. There are two points to note here.
At the beginning of the algorithm, the deque is a deque, so add the index of the element by the size of the first window.
If the element you add is smaller than the element after the deque, the element you add will be the last element of the new deque. If the element to add is larger, pop the element repeatedly from behind the deque until you find a larger element. Push the new element you want to add as the end.
As you can see, the deque stores the elements in descending order. The deque begins with the index of the maximum value for that particular window.
Repeat the following steps each time the window moves to the right.
Code
Recommended Posts