A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.
The array is [1 3 -1 -3 5 3 6 7], and w is 3.
Removing redundant elements and storing only elements that need to be considered in the queue is the key to achieve the efficient O(n) solution below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void maxSlidingWindow(int A[], int n, int w, int B[]) {
deque<int> Q;
for (int i = 0; i < w; i++) {
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
Q.push_back(i);
}
for (int i = w; i < n; i++) {
B[i-w] = A[Q.front()];
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
while (!Q.empty() && Q.front() <= i-w)
Q.pop_front();
Q.push_back(i);
}
B[n-w] = A[Q.front()];
}
|
The above algorithm could be proven to have run time complexity of O(n). This is because each element in the list is being inserted and then removed at most once. Therefore, the total number of insert + delete operations is 2n.
Read full article from Sliding Window Maximum | LeetCode
No comments:
Post a Comment