link ：https://leetcode.cn/problems/qIsx9U/solution/chun-c-by-xun-ge-v-80l5/
source ： Power button （LeetCode） 

subject

Example

Ideas

Their thinking
The title requires that a sliding window be maintained , At the same time, it is necessary to ensure that the data is advanced and backward , Maintaining the sliding window size also requires first in and last out -> Ring queues are preferred
On each call next You need to make statistics on the data in the sliding window , The sliding window needs to be calculated repeatedly , You can use prefixes and for memorized searches
You need to maintain the size of the sliding window , When new data comes , You need to kick out the advanced data in the queue , Just meet the requirements of ring queue , That is, the window size is maintained , You can also update the data

Code

typedef struct {
    double * ans;// The circular queue ,i % size ->  Ring queues store data 
    double prefix;// The prefix and 
    int inode;// Queue subscript 
    int asize;// Queue size 
    bool full;// Is the queue full 
} MovingAverage;

/** Initialize your data structure here. */
// Initialize structure 
MovingAverage* movingAverageCreate(int size) {
    MovingAverage * obj = malloc(sizeof(MovingAverage));
    obj->ans = malloc(sizeof(double) * size);
    memset(obj->ans, 0, sizeof(double) * size);
    obj->inode = 0;
    obj->asize = size;
    obj->prefix = 0;
    obj->full = false;// The queue is under 
    return obj;
}

double movingAverageNext(MovingAverage* obj, int val) {
    if(obj->inode == obj->asize)// Whether the queue is full 
    {
        obj->full = true;
        obj->inode = 0;
    }
    obj->prefix -= obj->ans[obj->inode];// Prefix and subtract the current position first 
    obj->ans[obj->inode++] = (double)val;// The team 
    obj->prefix += (double)val;// Add prefix and 
    if(obj->full == true)// Queue full divide all 
    {
        return obj->prefix / obj->asize;
    }
    return obj->prefix / obj->inode;
}

void movingAverageFree(MovingAverage* obj) {
    free(obj->ans);
    free(obj);
}

/**
 * Your MovingAverage struct will be instantiated and called as such:
 * MovingAverage* obj = movingAverageCreate(size);
 * double param_1 = movingAverageNext(obj, val);
 
 * movingAverageFree(obj);
*/

Time and space complexity