2024-09-03
Given an array of length n, is it possible to output the maximum value of every consecutive k numbers (A[i, i+k-1]) in O(n) time?
One idea is to dynamically maintain a queue that satisfies at any time i:
The elements in the queue come from A[i, i+k-1]
A[s] is in the queue if and only if all elements in A(s, i+k-1] are less than A[s]. Specifically, A[i+k-1] must be at the end of the queue.
It is not difficult to see that the "head" or the leftmost element of the queue is the maximum value of A[i, i+k-1].
Each time i is increased, you only need to:
Start from the end of the original queue and pop out elements that are not greater than A[i+k], then let A[i+k] enter the end of the queue
Check if the head element is A[i], if so, pop it out
Each element enters and exits the queue at most once, so the algorithm is O(N).
The sliding window algorithm has many types, such as fixed-length windows, finding the shortest window, finding the longest window, etc.
Use two pointers lp, rp to define the current window as A[lp, rp), so moving the left and right ends is very simple:
add A[rp] to window
rp = rp + 1
remove A[lp] from window
lp = lp + 1
Given an array of length n, how small can the complexity be to output the x-th smallest number in every consecutive k numbers (A[i, i+k-1])? Related example: Leetcode 2653.
One idea is to maintain two balanced search trees to store the numbers in the window, the first tree of size x, and the second tree of size k-x, ensuring that at any time the elements in the first tree are all less than those in the second tree. Thus, the maximum value of the first tree is the x-th smallest number in the window.
Each time the window moves, you need to delete one element and add one element:
If the deleted element is in the first tree and the added element is less than the smallest element in the second tree, insert the added element into the first tree. The symmetric situation is similar.
If the deleted element is in the first tree and the added element is greater than the smallest element in the second tree, transfer the smallest element from the second tree to the first tree, and insert the added element into the second tree. The symmetric situation is similar.
Doing so requires O(n(log(x)+log(k-x))) or O(n log k) complexity. Using heaps (priority queues) will not reduce its complexity, although it may improve actual performance.
If using the interface of a fully ordered vector, such as sortedcontainers, this problem can also be solved directly: each time the window moves, adding and deleting an element takes $O(k^{1/3})$; then reading the k-th smallest number takes O(1). The overall time complexity is $O(n k^{1/3})$.
The characteristic of this type of problem: if a window satisfies the condition, then all its sub-windows satisfy the condition. Specifically, windows of length 1 satisfy the condition.
# Must be able to add any element when window is empty
lp, rp = 0, 0
while rp < len(A)
while cannot add A[rp] to window
remove A[lp] from window
lp = lp + 1
add A[rp] to window
rp = rp + 1
A[lp, rp) is a new valid window
Example: Longest substring without repeating characters / where each character appears at most k times
The characteristic of this type of problem: if a window satisfies the condition, then any window containing this window satisfies the condition. Specifically, an empty window does not satisfy the condition. Find the minimum window.
# Empty window (lp == rp) must not satisfy condition
lp, rp = 0, 0
while True:
while rp < len(A) and condition is not satisfied
add A[rp] to window
rp = rp + 1
if condition is not satisfied
break # we reached the end
while lp < rp and condition is satisfied
A[lp, rp) is a new valid window
remove A[lp] from window
lp = lp + 1
Example: Flowerpot (Luogu P2698) Given a series of points (x, y) on a plane, find the shortest x interval such that the range of y coordinates on this interval is not less than D
A typical example is two pointers starting from both ends of the array and moving towards the middle.
Example: 3Sum. Find all triplets in an integer array that sum to 0. First, sort the array to facilitate subsequent pointer searches. Choosing three numbers requires three pointers; suppose we fix the leftmost pointer p, then there are two pointers l, r left. Let l start moving right from p+1, and r start moving left from the right end of the array. If the sum of the three numbers is greater than 0, move r; if less than 0, move l, until l >= r. This way, all l, r that meet the requirements for a specific p can be found in O(n) time.