kiddy

max num in the sliding window

leave a comment »

vector<int> maxSlidingWin(vector<int> input, int k){
	vector<int> ret;
	ret.clear();
	deque<int> qq;
	int size = input.size();
	if(size == 0 | size < k)	return ret;
	for(int i = 0; i < size; i++){
		int cur = input[i];
		while(!qq.empty() && cur > input[qq.back()]){
			qq.pop_back();
		}
		qq.push_back(i);

		while(!qq.empty() && qq.front() <= i-k){
			qq.pop_front();
		}

		if(i >= k-1){
			ret.push_back(input[qq.front()]);
		}
	}
	return ret;
}

void printvec(vector<int> &ret){
	int size = ret.size();
	for(int i = 0; i < size; i++){
		cout<<ret[i]<<" ";
	}
}

int main(){
	int a[] = {2,3,5,2,4,3,2,6};
	vector<int> input(a,a+8);
	vector<int> ret = maxSlidingWin(input, 3);
	printvec(ret);
	return 0;
}

http://leetcode.com/2011/01/sliding-window-maximum.html

Advertisements

Written by linzhongzl

December 26, 2013 at 12:17 pm

Posted in Others

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: