分为两个主要模块,要在一个滑动窗口中找最小值,以及最大值。
那么你需要去维护两个单调队列,一个是单调递增的队列,一个是单调递减的队列!
得到最小值:
//要写一个单调递增的单调队列得到最小值 void getMin() { memset(que, 0, sizeof(que)); que[0].value=-INF; int r=1,l=1; for(int i=1;i<=k;i++){ while(que[r].value>=arr[i]&&l<=r){//单调递增 r--; } que[++r].value=arr[i];//入队 que[r].pos=i; } for(int i=k;i<=n;i++){ while(que[r].value>=arr[i]&&l<=r){//单调递增 r--; } que[++r].value=arr[i];//入队 que[r].pos=i; while(que[l].pos<=i-k){ l++; } printf("%d ",que[l].value); } }
得到最大值
void getMax() { memset(que, 0, sizeof(que)); que[0].value=INF; int r=1,l=1; for(int i=1;i<=k;i++){ while(que[r].value<=arr[i]&&l<=r){//单调递增 r--; } que[++r].value=arr[i];//入队 que[r].pos=i; } for(int i=k;i<=n;i++){ while(que[r].value<=arr[i]&&l<=r){//单调递增 r--; } que[++r].value=arr[i];//入队 que[r].pos=i; while(que[l].pos<=i-k){ l++; } printf("%d ",que[l].value); } }
ac代码:
#include#include #include using namespace std; const int maxn = 1e6+10; const int INF = 0x3f3f3f3f; int n,k; //开一个结构体,存位置和数值 struct node{ int pos; int value; }que[maxn]; //开一个数组存要存的num int arr[maxn]; //要写一个单调递增的单调队列得到最小值 void getMin() { memset(que, 0, sizeof(que)); que[0].value=-INF; int r=1,l=1; for(int i=1;i<=k;i++){ while(que[r].value>=arr[i]&&l<=r){//单调递增 r--; } que[++r].value=arr[i];//入队 que[r].pos=i; } for(int i=k;i<=n;i++){ while(que[r].value>=arr[i]&&l<=r){//单调递增 r--; } que[++r].value=arr[i];//入队 que[r].pos=i; while(que[l].pos<=i-k){ l++; } printf("%d ",que[l].value); } } //要写一个单调递减的单调队列得到最大值 void getMax() { memset(que, 0, sizeof(que)); que[0].value=INF; int r=1,l=1; for(int i=1;i<=k;i++){ while(que[r].value<=arr[i]&&l<=r){//单调递增 r--; } que[++r].value=arr[i];//入队 que[r].pos=i; } for(int i=k;i<=n;i++){ while(que[r].value<=arr[i]&&l<=r){//单调递增 r--; } que[++r].value=arr[i];//入队 que[r].pos=i; while(que[l].pos<=i-k){ l++; } printf("%d ",que[l].value); } } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); } getMin(); printf("n"); getMax(); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)