题目描述
给定一个大小为 n≤106
的数组。
有一个大小为 k
的滑动窗口,它从数组的最左边移动到最右边。
你只能在窗口中看到 k
个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子:
该数组为 [1 3 -1 -3 5 3 6 7],k
为 3
。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。
样例
8 3
1 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
算法 (优先队列)
还没看到有人发这个方法的题解
C++ 代码
include[HTML_REMOVED]
using namespace std;
typedef pair[HTML_REMOVED]pll;
int a[1200000];
priority_queue[HTML_REMOVED]q;//大顶堆
priority_queue[HTML_REMOVED],greater[HTML_REMOVED]>qe;//小顶堆
int main()
{
int n,k;
cin>>n>>k;
for(int t=1;t<=n;t++) cin>>a[t];
for(int t=1;t<=n;t++)
{
if(t<k) qe.push({a[t],t});
else
{
qe.push({a[t],t});//直接可以放进去
while(qe.top().second<=t-k&&qe.size()) qe.pop();
cout<<qe.top().first<<' ';
}
}
cout<<endl;
for(int t=1;t<=n;t++)
{
if(t<k) q.push({a[t],t});
else
{
q.push({a[t],t});
while(q.size()&&q.top().second<=t-k) q.pop();
cout<<q.top().first<<' ';
}
}
}