by this time, the summer vacation left only 7 weeks. 

what did i do for past 3 weeks -_-?

omg.........

Problem Introduction

The algorithm is sometimes also referred to as the Ascending Minima algorithm. I learnt the algorithm from a South African Computer Olympiad camp some years ago. I couldn't find any references to it in any journal, however there are some explanations on the Internet.

Given an array ARR and an integer K, the problem boils down to computing for each index i: min(ARR[i], ARR[i-1], ..., ARR[i-K+1]). The algorithm for this "slides" a "window" of size K over ARR computing at each step the current minimum. In other words the algorithm roughly follows this psuedocode:

for (i = 0; i < ARR.size(); i++) {
  remove ARR[i-K] from the sliding window
  insert ARR[i] into the sliding window
  output the smallest value in the window
}

The sliding window algorithm does the remove, insert and output step in amortized constant time. Or rather the time it takes to run the algorithm is O(ARR.size()).

Sliding Window Minimum Algorithm

The idea of lazily deleting elements is a salient one, but by putting in a bit more effort when inserting an element into the window we can get amortized O(1) run-time. Say our window contains the elements {1, 6, 7, 2, 4, 2}. We want to add the element 5 to our window. Notice that all elements in the window greater than 5 will now never be the minimum in the window for future i values, so we might as well get rid of them. The trick to this is to store the numbers in a deque [1] and whenever inserting a number x we remove all numbers at the back of the deque which are greater than equal to x. Notice that if the deque was sorted before inserting, it will still be sorted after inserting x. Since the deque starts off sorted, it remains sorted throughout the sliding window algorithm. So the front of the deque will always be the smallest value.

The front of the queue might have a value which shouldn't be in the window anymore, but we can use the lazy delete idea with the deques as well. Now each element of ARR is inserted into the deque and deleted from the deque at most once. This gives as a total run-time of O(N) for the algorithm (amortized O(1) per insertion/deletion). Pretty sweet:

void sliding_window_minimum(std::vector<int> & ARR, int K) {
  // pair<int, int> represents the pair (ARR[i], i)
  std::deque< std::pair<int, int> > window;
  for (int i = 0; i < ARR.size(); i++) {
     while (!window.empty() && window.back().first >= ARR[i])
       window.pop_back();
     window.push_back(std::make_pair(ARR[i], i));

     while(window.front().second <= i - K)
       window.pop_front();

     std::cout << (window.front().first) << ' ';
  }
}

source : http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html#sliding-window-minimum-algorithm