LCR041-LCR042队列的应用

剑指offer（专项突破版）7.2 队列的应用

LCR041.滑动窗口的平均值

分析

题目给出的例子中的删除规则是把最早添加进来的数字删除，因此这是一种“先入先出”的顺序，由此想到应该采用队列这种数据结构来表示滑动窗口。

class MovingAverage {
public:
    /** Initialize your data structure here. */
    int capacity = 0;
    queue<int> que;
    double sum = 0;

    MovingAverage(int size) {
        capacity = size;
    }
    
    double next(int val) {
        que.push(val);
        sum += val;
        if(que.size() > capacity){
            sum -= que.front();
            que.pop();
        }
        return sum / que.size();
    }
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

• 时间复杂度：对于每次插入元素操作都只需要常数时间，O(1)。
• 空间复杂度：O(n)。

LCR042.最近的请求次数

分析

每次调用ping，先检查t-3000是否小于等于队头，如果大于队头则说明已不在3000秒内，就不断把队头移出，直到小于等于队头，入队，并返回队列的长度。

class RecentCounter {
public:
    queue<int> que;
    RecentCounter() {

    }
    
    int ping(int t) {
        while(!que.empty() && t-3000 > que.front()){
            que.pop();
        }
        que.push(t);
        return que.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

假设计数器时间窗口的大小是w毫秒，其中记录的时间是递增的，那么时间窗口中记录的时间的数目是O（w），因此空间复杂度是O（w）。每当收到一个新的请求ping时，由于可能需要删除O（w）个已经滑出时间窗口的请求，因此时间复杂度也是O（w）。但是由于这个题目中时间窗口的大小为3000毫秒，w是一个常数，因此也可以认为时间复杂度和空间复杂度都是O（1）。