单调队列初步

2017年07月15日 9点热度 0人点赞 0条评论

题意: 
求滑动窗口中的最大值和最小值。 
分析: 
可以用线段树来做,建完树后,查询区间n-k+1次就行。 
也可以用单调队列来做,比如求窗口中的最小值,那么就维护一个递增的队列,那么最小元素就是队首元素,每次右移,只要维护队列元素是递增的就可以。同样,求最大值,是维护一个递减的队列。

#include
#include
#include
using namespace std;
const int N=1e6+9;
#define pos first
#define val second
#define mp make_pair
typedef pair<int,int>pii;
pii q[N];
int a[N];
int n,k;
void getmin()
{
    int l=1,r=0,i=0;
    for(;iwhile(r>=l&&q[r].val>a[i])r--;
        q[++r]=mp(i,a[i]);
    }
    printf("%d",q[l].val);
    for(;iif(q[l].pos1)l++;
        while(r>=l&&q[r].val>a[i])r--;
        q[++r]=mp(i,a[i]);
        printf(" %d",q[l].val);
    }
    printf("n");
}
void getmax()
{
    int l=1,r=0,i=0;
    for(;iwhile(r>=l&&q[r].valq[++r]=mp(i,a[i]);
    }
    printf("%d",q[l].val);
    for(;iif(q[l].pos1)l++;
        while(r>=l&&q[r].valq[++r]=mp(i,a[i]);
        printf(" %d",q[l].val);
    }
    printf("n");
}
int main()
{
    //freopen("f.txt","r",stdin);
    while(~scanf("%d%d",&n,&k)){
        for(int i=0;i"%d",&a[i]);
        getmin();
        getmax();
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
未经允许不得转载!单调队列初步

update

纸上得来终觉浅, 绝知此事须躬行。