题目描述：http://poj.org/problem?id=2823
思路：
求某个区间的最大与最小值，可以使用两个单调队列，由于需要在队列前删除元素和在队列后增加元素，所以考虑使用双端队列；
在双端队列中记录元素的下标，另外，双端队列为单调队列，满足单调非递增或单调非递减，则队列第一个元素为区间最大或最小元素；
这样可以找出区间中的最大与最小值。该算法为线性时间,时间复杂度为O(N)。
代码：
#include <iostream> #include <deque> #define MAX_N ( 100000 + 10 ) using namespace std; int A[MAX_N]; deque<int> D( MAX_N ); void MaxOfSliding( int n, int k ); void MinOfSliding( int n, int k ); int main( ) { int n, k; while ( scanf( "%d %d", &n, &k ) != EOF ) { for ( int i = 0; i < n; ++i ) scanf( "%d", &A[i] ); MinOfSliding( n, k ); MaxOfSliding( n, k ); } return 0; } void MaxOfSliding( int n, int k ) { int i; for ( i = 0; i < k - 1; ++i ) { if ( !D.empty( ) && A[i] > D.back( ) ) D.pop_back( ); D.push_back( i ); } for ( i = k - 1; i < n; ++i ) { while ( !D.empty( ) && i - D.front( ) >= k ) D.pop_front( ); while ( !D.empty( ) && A[i] > D.back( ) ) D.pop_back( ); D.push_back( i ); printf( "%d ",A[D.front( )] ); } D.clear( ); printf( "\n" ); } void MinOfSliding( int n, int k ) { int i; for ( i = 0; i < k - 1; ++i ) { if ( !D.empty( ) && A[i] < D.back( ) ) D.pop_back( ); D.push_back( i ); } for ( i = k - 1; i < n; ++i ) { while ( !D.empty( ) && i - D.front( ) >= k ) D.pop_front( ); while ( !D.empty( ) && A[i] < D.back( ) ) D.pop_back( ); D.push_back( i ); printf( "%d ", A[D.front( )] ); } D.clear( ); printf( "\n" ); }