解题思想与代码实现,令人叹为观止 队列的最佳应用 从总体上讲,完成代码的思路是非常清晰的
根据窗口大小,从源数据第一个开始,把数据依次压入队列中 从压入队列的数据中找出最大值,放入结果集合中 再将队列中第一个元素弹出,从尾部压入下一个元素,然后再找出当前队列中的最大值,放入结果集合中 如此反复,直到最后一个元素 双端队列的性质的应用
滑动窗口最多放入的数据不超过窗口长度 队列中的最前面的元素就是当前队列的最大值
保证最大值在队列最前面的前提是,当数据被压住队列时,把比压入数据小的,且排在队列前面的元素全都弹出队列 在循环压入数据过程中,正常是应该把队列中最前面元素弹出,但由于上一步已有把小的元素弹出队列的操作,所以这一步弹出队列第一个元素的操作可能是虚晃一枪,因为可能不需要真实删除元素,只是在有必要时才进行弹出操作
# include <iostream>
# include <vector>
# include <deque>
class SlidingWindowDes {
private :
std:: deque< int > que;
public :
void pop ( int value) {
if ( ! que. empty ( ) && que. front ( ) == value)
que. pop_front ( ) ;
}
void push ( int value) {
while ( ! que. empty ( ) && value > que. back ( ) )
que. pop_back ( ) ;
que. push_back ( value) ;
}
int getFront ( ) {
return que. front ( ) ;
}
} ;
class Solution {
public :
std:: vector< int > maxSlidingWindow ( std:: vector< int > & nums, int k) {
SlidingWindowDes swd;
std:: vector< int > vec_result;
for ( int i = 0 ; i < k; i++ )
swd. push ( nums. at ( i) ) ;
vec_result. push_back ( swd. getFront ( ) ) ;
for ( int i = k; i < nums. size ( ) ; ++ i) {
swd. pop ( nums. at ( i - k) ) ;
swd. push ( nums. at ( i) ) ;
vec_result. push_back ( swd. getFront ( ) ) ;
}
return vec_result;
}
} ;
int main ( )
{
std:: vector< int > nums { 1 , 3 , - 1 , - 3 , 5 , 3 , 6 , 7 } ;
Solution s;
std:: vector< int > ret = s. maxSlidingWindow ( nums, 3 ) ;
for ( int e: ret)
std:: cout << e << " " ;
std:: cout << std:: endl;
return 0 ;
}