EndlessLethe原创文章,转载请注明: 转载自小楼吹彻玉笙寒
本文链接地址: 浅谈【剑指offer】滑动窗口的最大值
题目
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
Note:题目没有说明,但是边界条件 size > num.size() or size <= 0,都需要直接返回空的vector。
四种解法
- 暴力,时间复杂度O(n*size)
- 线段树,时间复杂度O(nlogn+nlogn)
- 用两个优先队列,一个容纳size中的元素pq1,一个容纳已滑动删除的元素pq2。每次滑动时,看当前元素t和pq1.top()的大小,如果相等,则弹出,否则加入pq2。时间复杂度为O(n logn)
- 维护一个单调队列,单调队列模板题,维护滑动区间的区间最值。时间复杂度O(n)
不会单调队列的可以戳”单调队列和单调栈详解”
实现代码
单调队列 O(n)
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> res;
if (size > num.size()) return res;
if (size <= 0) return res;
int mq[100000] = {0};
int l = 0, r = 0;
// mq[0]不储存值 mq[r]为当前队列的最后一个
// 因为是维护最大值,所以需要单调递减的队列
for (int i = 0; i < size; i++) {
while (l < r && mq[r] < num[i]) --r;
mq[++r] = num[i];
}
res.push_back(mq[l+1]);
for (int i = size; i < num.size(); i++) {
if (l < r && num[i-size] == mq[l+1]) l++;
while (l < r && mq[r] < num[i]) --r;
mq[++r] = num[i];
res.push_back(mq[l+1]);
}
return res;
}
};
优先队列 O(nlogn)
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> res;
if (size > num.size()) return res;
if (size <= 0) return res;
priority_queue<int> pq1, pq2;
for (int i = 0; i < size; i++) {
pq1.push(num[i]);
}
res.push_back(pq1.top());
// printf("%d\n", num.size());
for (int i = size; i < num.size(); i++) {
// printf("i %d pq1.size %d pq1.top %d\n", i, pq1.size(), pq1.top());
if (num[i-size] == pq1.top()) {
pq1.pop();
// 先删后加,让pq2尽可能小一点
while (!pq2.empty() && pq2.top() == pq1.top()) {
pq2.pop();
pq1.pop();
}
}
else {
pq2.push(num[i-size]);
}
pq1.push(num[i]);
res.push_back(pq1.top());
// printf("add %d\n", pq1.top());
}
return res;
}
};