题解 | #滑动窗口的最大值#

#include <cstddef>
#include <stdexcept>
typedef struct QNode{
    int data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

int InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(-1);
    Q.front->next = NULL;
    return 1;
}

int DeQueue(LinkQueue &Q){
    if(Q.front == Q.rear) return 0;
    QueuePtr p = Q.front->next;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front;
    free(p);
    return 1;
}

int EnQueue(LinkQueue &Q, int e){
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(-1);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return 1;
}

void Max(LinkQueue &Q, vector<int> &max, int size, int n){
    if(size==1) {
        max[n] = Q.front->next->data;
        return;
    } else{
        QueuePtr p = Q.front->next;
        max[n] = p->data;
        for(int i = 0;i<size-1;i++){
        if(max[n]<p->next->data)  max[n] = p->next->data;
        p = p->next;
        }
    }
}

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        int n = num.size();
        vector<int> max(n-size+1);
        if((size==0)||(size>n)) return {};
        LinkQueue Q;
        InitQueue(Q);
        for(int i=0;i<size;i++){
            EnQueue(Q, num[i]);
        }
        Max(Q, max, size, 0);
        for(int i = 1;i<n-size+1;i++){
            DeQueue(Q);
            EnQueue(Q, num[size+i-1]);
            Max(Q, max, size, i);
        }
        return max;
    }
};