POJ - 2823 Sliding Window（单调栈）

Sliding Window

双端队列写法需要用C++提交，G++会超时

#include<cstdio>
#include<deque>
using namespace std;
const int N=1000010;
deque<int> q;
int main(void)
{
    int n,k,a[N];scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d",&a[i]);for(int i=0;i<n;i++)// 维护窗口最小值// 判断是否已经滑出窗口{
    if(!q.empty()&&i-k+1>q.front()) q.pop_front();while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back();q.push_back(i);if(i+1>=k) printf("%d ",a[q.front()]);}puts("");q.clear();for(int i=0;i<n;i++)// 维护窗口最大值// 判断是否已经滑出窗口{
    if(!q.empty()&&i-k+1>q.front()) q.pop_front();while(!q.empty()&&a[q.back()]<=a[i]) q.pop_back();q.push_back(i);if(i+1>=k) printf("%d ",a[q.front()]);}return 0;
}

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int a[1000011];//数组数据
int OutMin[1000011];//最小值
int OutMax[1000011];//最大值
int cnt1=0,cnt2=0;
int n,k;
struct cmp1
{
    bool operator()(const int a1,const int a2){
    return a[a1]>a[a2];}
};
struct cmp2
{
    bool operator()(const int a1,const int a2){
    return a[a1]<a[a2];}
};
priority_queue<int,vector<int>,cmp1>Q1;//最大优先 
priority_queue<int,vector<int>,cmp2>Q2;//最小优先 
int main()
{
    int i;scanf("%d%d",&n,&k);if(k>n) k=n;for(i=1;i<=n;++i) scanf("%d",&a[i]);for(i=1;i<=k;++i){
    Q1.push(i);//按数值大小入队，入队的是时间Q2.push(i);}OutMin[cnt1++]=a[Q1.top()];//把队首元素提取出来OutMax[cnt2++]=a[Q2.top()];for(i=k+1;i<=n;++i)//向后移动{
    Q1.push(i);Q2.push(i);while(i-Q1.top()>=k)//如果队首元素过期了，就删除队首元素Q1.pop();OutMin[cnt1++]=a[Q1.top()];//储存删除之后的队首元素while(i-Q2.top()>=k)Q2.pop();OutMax[cnt2++]=a[Q2.top()];}for(i=0;i<=(n-k);++i) printf("%d ",OutMin[i]); puts("");for(i=0;i<=(n-k);++i) printf("%d ",OutMax[i]); return 0;
}