239. Sliding Window Maximum

Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position.

S1: heap (STL:: multiset/ map) O(nlogk)

S2: deque 双端队列O(n)

维护一个递减的双端index队列，队首index对应的元素即为max。每次push_back之前popback所有比当前值小的元素，因为当前push_back进的元素至少会存在之后k-1次move中，所以在它之前比它小的数都不可能是所求max

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> idx;
        for (int i = 0; i < nums.size(); ++i) {
            while(!idx.empty() && nums[idx.back()] <= nums[i]) {
                idx.pop_back();
            }
            idx.push_back(i);
            if (i - k == idx.front()) {
                idx.pop_front();
            }
            if (i >= k - 1) {
                result.push_back(nums[idx.front()]);
            }
        }
        return result;
    }

346. Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

For example,

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

S: queue O(n)

class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        sum = 0;
    }

    double next(int val) {
        if (nums.size() < maxSize) {
            nums.push(val);
            sum += val;
            return (double)sum / nums.size();
        } else {
            sum -= nums.front();
            sum += val;
            nums.pop();
            nums.push(val);
            return (double)sum / maxSize;
        }
    }
    queue<int> nums;
    int maxSize;
    int sum;
};