C语言用双向链表实现单调递减（递增）队列

参考代码

#include<stdio.h>#include<stdlib.h>typedefstructNode{intnum;intindex;structNode*prev;structNode*next;}Node;typedefstructMonoDeQueue{intsize;Node*begin;Node*end;}MonoDeQueue;voidEnqueue(MonoDeQueue*q,intvalue,intindex){Node*node=(Node*)malloc(sizeof(Node));node->num=value;node->index=index;node->prev=NULL;node->next=NULL;if(q->size==0){q->begin=node;q->end=node;q->size++;return;}Node*cur=q->end;Node*temp=NULL;//只需将循环条件改为下面的条件，即可实现单调递增队列// while (cur && cur->num >= value) {while(cur&&cur->num<=value){if(q->size==1){free(cur);q->begin=NULL;q->end=NULL;q->size=0;cur=NULL;break;}temp=cur->prev;free(cur);cur=temp;q->size--;}if(cur){cur->next=NULL;q->end=cur;}if(q->size==0){q->begin=node;q->end=node;}else{q->end->next=node;node->prev=q->end;q->end=node;}q->size++;}voidDequeue(MonoDeQueue*q){if(q->size==0){return;}if(q->size==1){free(q->begin);q->begin=NULL;q->end=NULL;q->size=0;return;}Node*temp=q->begin->next;free(q->begin);q->begin=temp;q->begin->prev=NULL;q->size--;}voidfreequeue(MonoDeQueue*q){if(q->size==0){return;}Node*cur=q->begin;Node*temp=NULL;while(cur){temp=cur->next;free(cur);cur=temp;}q->begin=NULL;q->end=NULL;q->size=0;}voiditerator(MonoDeQueue*q){if(q->size==0){printf_s("The MonoDeQueue is now empty!!!\r\n");return;}Node*cur=q->begin;while(cur){printf_s("%d ",cur->num);cur=cur->next;}printf_s("\r\n");}intmain(){intnum[]={5,4,3,2,1,7};MonoDeQueue q={0,NULL,NULL};for(inti=0;i<sizeof(num)/sizeof(num[0]);++i){Enqueue(&q,num[i]);}iterator(&q);clear(&q);iterator(&q);return0;}

运行结果

利用上述实现的单调递减队列求解Leetcode 239. 滑动窗口最大值

int*maxSlidingWindow(int*nums,intnumsSize,intk,int*returnSize){intsize=numsSize-k+1;intindex=0;int*result=(int*)malloc(sizeof(int)*size);MonoDeQueue q={0,NULL,NULL,};for(inti=0;i<k;i++){Enqueue(&q,nums[i],i);}result[index++]=q.begin->num;for(inti=k;i<numsSize;i++){if(q.begin->index==i-k){Dequeue(&q);}Enqueue(&q,nums[i],i);result[index++]=q.begin->num;}freequeue(&q);*returnSize=size;returnresult;}

得到