LeetCode热题100：单调队列

摘要

题目	知识点
239. 滑动窗口最大值 - 力扣（LeetCode）	单调队列

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

1）STL实现

class Solution {
public:	
    // {数值，插入时间}
	deque<pair<int,int> > dq;
	
	// 单调队列插入
	void push(int x, int i){
		while(!dq.empty() && dq.back().first <= x){
			dq.pop_back();
		}
		dq.push_back({x, i});
	}	
	
	// 单调队列取最值
    // 取出队首一个时间在范围内的数
	int getMax(int i, int k){
		while(!dq.empty() && dq.front().second <= i - k){
			dq.pop_front();
		}
		if(!dq.empty()) return dq.front().first;
		else return -1;
	}
	
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		vector<int > ans;
		for(int i = 0 ; i < k ; i ++){
			push(nums[i], i);
		}
		ans.push_back(getMax(k-1, k));
		for(int i = k ; i < nums.size() ; i ++){
			push(nums[i], i);
			ans.push_back(getMax(i, k));
		}
		return ans;
	}
};

2）数组实现

class Solution {
	public:	
	vector<pair<int,int> > q;
	int h, t;
	// 单调队列插入
	void push(int x, int i){
		while(t >= h && q[t].first <= x){
			t--;
		}
		q[++t] = {x, i};
	}	
	
	// 单调队列取最值
	int getMax(int i, int k){
		while(h <= t && q[h].second <= i-k){
			h++;
		}
		if(h <= t) return q[h].first;
		return -1;
	}
	
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		q.resize(nums.size());
		h = 0; t = -1;
		vector<int > ans;
		for(int i = 0 ; i < k ; i ++){
			push(nums[i], i);
		}
		ans.push_back(getMax(k-1, k));
		for(int i = k ; i < nums.size() ; i ++){
			push(nums[i], i);
			ans.push_back(getMax(i, k));
		}
		return ans;
	}
};