滑动窗口最大值

【道德经·第三十七章】道常无为而无不为。候王若能守之，万物将自化。化而欲作，吾将镇之以无名之朴，镇之以无名之朴，夫将不欲。不欲以静，天下将自定。

剑指 Offer II 041. 滑动窗口的平均值

给定一个整数数据流和一个窗口大小，计算滑动窗口里所有数字的平均值。

class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        sz = size;
    }
    
    double next(int val) {
        if(dq.size() == sz) {
            sum -= dq.front();
            dq.pop_front();
        }
        
        sum += val;
        dq.push_back(val);
        
        return sum/dq.size();
    }
    
private:
    int sz = 0;
    double sum = 0;
    deque<double> dq;
    
};

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

239. 滑动窗口最大值

求滑动窗口最大值

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;

        int n = nums.size();
        if(n<k || k<1) return res;

        deque<int> dq;
        for(int i = 0; i < n; i++) {
            while(!dq.empty() && nums[dq.back()]<nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);
            if(dq.front()+k == i) {
                dq.pop_front();
            }

            if(i >= k-1) {
                res.push_back(nums[dq.front()]);
            }
        }

        return res;
    }
};

位我上者，灿烂星空；道德律令，在我心中。