题目描述
给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。
示例:
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3
题解
用队列，超过窗长时，减去头指针的值，加上新入队的值，更新队列指针。
注意返回值为double。
typedef struct {
int *val;
int head;
int tail;
int size;
int len;
double sum;
} MovingAverage;
/** Initialize your data structure here. */
MovingAverage* movingAverageCreate(int size) {
MovingAverage *moving;
if (size == 0) {
return 0;
}
moving = (MovingAverage *)malloc(sizeof(MovingAverage));
moving->val = (int *)malloc(sizeof(int) * size);
moving->size = size;
moving->len = 0;
moving->head = 0;
moving->tail = -1;
moving->sum = 0;
return moving;
}
double movingAverageNext(MovingAverage* obj, int val) {
double sum = obj->sum;
if (obj->len < obj->size) {
sum += val;
obj->tail = (obj->tail + 1) % obj->size;
obj->val[obj->tail] = val;
obj->sum = sum;
obj->len++;
} else {
sum -= obj->val[obj->head];
sum += val;
obj->tail = (obj->tail + 1) % obj->size;
obj->val[obj->tail] = val;
obj->head = (obj->head + 1) % obj->size;
obj->sum = sum;
}
return sum/obj->len;
}
void movingAverageFree(MovingAverage* obj) {
free(obj->val);
free(obj);
}