单调队列—————力扣239题
单调队列—————力扣239题
今天讲一种数据结构----单调队列。其实就是队列的特殊版本。队列里面的数，要么递增，要么递减。
class MonotonicQueue
{
deque<int> data;
public:
void push(int x)
{
while(!data.empty() && data.back()>x)//入队时，注意要入对的元素前不能有比它大（小）的元素
{
data.pop_back();//如果有，出队
}
data.push_back(x);
}
void pop(int n)
{
if(!data.empty() && data.front()==n)
{
data.pop_front();
}
}
int max()
{
return data.front();
}
};
力扣239题
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：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
刚好看见力扣的239题的滑动窗口寻找最大值用单调队列解决很简单
这道题不复杂，难点在于如何在 O(1) 时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成。在之前我们探讨过类似的场景，得到一个结论：
在一堆数字中，已知最值，如果给这堆数添加一个数，那么比较一下就可以很快算出最值；但如果减少一个数，就不一定能很快得到最值了，而要遍历所有数重新找最值。
回到这道题的场景，每个窗口前进的时候，要添加一个数同时减少一个数，所以想在 O(1) 的时间得出新的最值，就需要「单调队列」这种特殊的数据结构来辅助了。
一个普通的队列一定有这两个操作：
class Queue {
void push(int n);
// 或 enqueue，在队尾加入元素 n
void pop();
// 或 dequeue，删除队头元素
}
一个「单调队列」的操作也差不多：
class MonotonicQueue {
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}
当然，这几个 API 的实现方法肯定跟一般的 Queue 不一样，不过我们暂且不管，而且认为这几个操作的时间复杂度都是 O(1)，先把这道「滑动窗口」问题的解答框架搭出来：
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
MonotonicQueue window;
vector<int> res;
for(int i=0;i<nums.size();i++)
{
if(i<k-1)
{
window.push(nums[i]);
}
else
{
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i-k+1]);
}
}
return res;
}
算法复杂度分析
大家可能疑惑，push 操作中含有 while 循环，时间复杂度不是 O(1) 呀，那么本算法的时间复杂度应该不是线性时间吧？
单独看 push 操作的复杂度确实不是 O(1)，但是算法整体的复杂度依然是 O(N) 线性时间。要这样想，nums 中的每个元素最多被 push_back 和 pop_back 一次，没有任何多余操作，所以整体的复杂度还是 O(N)。
空间复杂度就很简单了，就是窗口的大小 O(k)。