Day4 plus 滑动窗口最大值

1.题目描述

链接：https://leetcode.cn/problems/sliding-window-maximum/description/

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

返回 滑动窗口中的最大值

2.示例

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

3.题目解析

优先级队列解法

因为要维护最大值，很容易的我们可以想到优先级队列，每次维护整个窗口的最大值。但是优先级队列需要注意的一个点就是，下标的大小。有可能第二大在窗口左边界的左边，那么这个时候是不能取这个最大值的，因此我们需要删除优先级队列中下标≤left 的节点

这里可以使用priority_queue<pair<int,int>>来维护窗口的最大值

单调栈

单调栈的思想很有意思，利用了一个思想，每次存储靠后下标的最大值，什么意思呢？

比如说 j>= i，同时 nums[j] ≥ nums[i]，那么这个时候是不是没有必要维护nums[i]了呢？

答案是 YES，因为 j和i在同一个窗口的时候，一定会有nums[j]为最大值，这个时候就没有必要去考虑nums[i]了，因此在栈中直接在尾部pop掉前面 i≤ j && nums[i]≤ nums[j]的节点

这个时候我们很容易知道栈的头部就是最大值，但是可能栈的头部已经超过窗口的边界了

因此我们需要弹出栈头部在左边界的值

so…可以用deque去实现头部和尾部的操作

4.代码实现

优先级队列

class Solution {
public:
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		const int N = nums.size();
		vector<int>res;
		//可以维护一个最大堆，每次将堆进行插入和删除
		int left = 0, right = k - 1;
		priority_queue<pair<int, int>>pq;
		for (int i = 0; i <= right; ++i)
			pq.push({ nums[i],i });
		res.emplace_back(pq.top().first);
		++right;
		while (right < N)
		{
			while (!pq.empty() && pq.top().second <= left)
				pq.pop();
			pq.push({ nums[right],right });
			++left, ++right;
			res.emplace_back(pq.top().first);
		}
		return res;
	}
};

单调栈

class Solution {
public:
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		const int N = nums.size();
		deque<int>dq;
		vector<int>res;
		int right = 0;
		for (; right < k; ++right)
		{
			while (!dq.empty() && nums[right] >= nums[dq.back()])
				dq.pop_back();
			dq.push_back(right);
		}
		res.push_back(nums[dq.front()]);
		while (right < N)
		{
			while (!dq.empty() && nums[right] >= nums[dq.back()])
				dq.pop_back();
			dq.push_back(right);
			while (dq.front() <= right - k)
				dq.pop_front();
			res.push_back(nums[dq.front()]);
            ++right;
		}
		return res;
	}
};