See the code
This file contains 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; | |
} |
Amortized complexity is O(n).
Problems to Solve:
- http://www.spoj.com/problems/ARRAYSUB/
- Task "sound" at http://www.boi2007.de/en/tasks
- Task "pyramid" at http://olympiads.win.tue.nl/ioi/ioi2006/contest/day1/ (medium to hard problem)
- http://wcipeg.com/problem/ccc03s2p5
- http://wcipeg.com/problem/ccc96s5
- http://wcipeg.com/problem/smac081p3
- http://wcipeg.com/problem/ccc96s5
- http://wcipeg.com/problem/ioi0611
- http://www.spoj.com/problems/BROKEN/
- http://www.spoj.com/problems/FSEATS/
- http://www.spoj.com/problems/KPMATRIX/
- http://www.spoj.com/problems/MATRIX2/
- http://www.codechef.com/problems/CHEFTOWN
- http://wcipeg.com/problem/ioi0612
- http://www.codechef.com/OCT12/problems/TEAMSIZE
- http://www.spoj.com/problems/KRECT/
- http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html
- http://softwarelearner.blogspot.in/2011/04/minima-in-sliding-window.html
- http://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples/8269948#8269948
- http://richardhartersworld.com/cri/2001/slidingmin.html
- http://wcipeg.com/wiki/Sliding_window
- http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
- http://wcipeg.com/wiki/Sliding_range_minimum_query
Thank you so much for sharing informative blog. Hope you continue to share more of your ideas. I will definitely love to read. Keep up the good work! Lorendo Portes et Fenêtres
ReplyDeleteI will visit your blog regularly for some latest post. Thanks for sharing,
ReplyDeleteMotorized Sliding Gate
ReplyDeleteAmazing Write up!. It’s a very helpful and nice information about windows & doors. This post helped me choose the perfect family room decorating. I would like to suggest to you the best Minimal Sliding Windows & Door System. Thanks for sharing this information. Keep Posting!
Good post! We are linking to this particularly great post on our website.
ReplyDeleteeducatorpage
Bloglovin
gumroad
toparticle
door site
Zenwriting