[Data Structure] CODE [VS] 4373 window (dual-end queue sliding window)

Click to get the window

The rubbish topic destroys my youth.

The word problem of the deque, the template problem of the sliding window?
Why are all playing simulations except me, I use STL???

The operation is performed while reading, the maximum and minimum operations are separated, and the subscript of the number is stored in the queue
If the time limit is over, pop up from the front.
When taking the minimum value, put the smallest at the head of the line. If the new element is smaller than the end of the line, it will be popped to the end, because you don’t need it.
When taking the maximum value, put the largest one at the head of the line. If the new element is larger than the end of the line, it will be popped up to the end, because you don’t need it. *2
Finally output, don’t forget to add between the numbers Spaces and line breaks

The code is as follows:

#include #include #include #include  #include #include #define maxn 1000006using namespace  std;int n,k;int num[maxn];int maxx[maxn],minn[maxn];de que<int >q1;deque< /span><int >q2;inline void rd(int &x){ scanf("%d",&x);}inline void work(){ < span class="hljs-keyword">for(int i = 1;i < = n;i++) {rd(num[i]); while(!q1.empty() && num[q1.back()] >= num[i ]) q1.pop_back(); q1.push_back(i); if(i >= k) {while(!q1.empty() && q1.front() <= (ik)) q1.pop_front(); minn[i] = num[q1.front()];} while(!q2.empty() && num[q2.back()] <= num[i]) q2.pop_back(); q2.push_back(i); if(i >= k) {while(!q2.empty() && q2.front() <= (ik) ) q2.pop_front(); maxx[i] = num[q2.front()];}} for(int  i = k;i <= n;i++) printf("%d ", minn[i]);puts("
"); for(int i = k;i <= n;i++) printf( "%d ",maxx[i]);puts("
");}int main(){ rd(n);rd(k); work();return 0;}

THE END

By Peacefuldoge

http://blog.csdn.net/loi_peacefuldog