Created
December 27, 2013 00:41
-
-
Save praveendhinwa/8140835 to your computer and use it in GitHub Desktop.
slidingWindow.cpp
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int N = 500005; | |
| int a[N]; | |
| int main() { | |
| int n, k; | |
| cin >> n >> k; | |
| for (int i = 0; i < n; i++) { | |
| cin >> a[i]; | |
| } | |
| deque <pair <int, int> > window; | |
| for (int i = 0; i < n; i++) { | |
| // from the back of deque, if the value of last element is greater or equal than a[i] | |
| // then keep poping the elements. | |
| // Invariant : deque always remains sorted. | |
| // Important property due to which this trick works, is that the popped numbers are useless | |
| // in the next iteration as they are not longer can affect minimum. | |
| while (!window.empty() && window.back().first >= a[i]) { | |
| window.pop_back(); | |
| } | |
| window.push_back (make_pair (a[i], i)); | |
| // Now from the front of deque, pop all the elements which were out of our window. | |
| while (!window.empty() && window.front().second <= i - k) { | |
| window.pop_front(); | |
| } | |
| if (i >= k - 1) | |
| cout << window.front().first << " "; | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment