Sliding Window Problem Summary (Lintcode 360, Leetcode 239)

做Sliding Window的方法是：将其拆解为“加一个元素，和减一个元素”。注意，有的时候最好先减再加，有的时候最好先加再减。而另外一个点是：很多情况下，并不用分类讨论 window size >= array size的情况，如下面两题。

Lintcode 360:

Sliding Window找median。这道题最好先减再加，用的是基本的two priority queue的方法。

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of the element inside the window at each moving
     */
    void insert(int num){
        if(m1.empty() || num <= *m1.begin()){
            m1.insert(num);
        }else{
            m2.insert(num);
        }
        balanceSet();
    } 
    
    void balanceSet(){
        if(m1.size() > m2.size() + 1){
            int cur = *m1.begin();
            m1.erase(m1.begin());
            m2.insert(cur);
        }
        if(m2.size() > m1.size()){
            int cur = *m2.begin();
            m2.erase(m2.begin());
            m1.insert(cur);
        }
    }
     
    void erase(int num){
        if(num <= *m1.begin()){
            m1.erase(m1.find(num));
        }else{
            m2.erase(m2.find(num));
        }
        balanceSet();
    } 
    vector<int> medianSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        vector<int> ret;
        if(nums.empty() || k <= 0) return ret;
        int idx = min(k, (int)nums.size());
        for(int i=0; i<idx; i++){
            insert(nums[i]);
        }
        ret.push_back(*m1.begin());
        for(int i=idx; i<nums.size(); i++){
            erase(nums[i - k]);
            insert(nums[i]);
            ret.push_back(*m1.begin());
        }
        return ret;
    }
private:
    multiset<int, greater<int>> m1;
    multiset<int> m2;
};

Sliding Window Maxium:

这道题用Deque解，而最好先加后减的顺序。基本思路是：记录一个max，如果这个max即将被deque pop出去，则扫一遍deque，找新的max。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> ret;
    deque<int> dq;
    if(nums.empty() || k <= 0) return ret;
    int max_num = nums[0];
    for(int i=0; i<min(k, (int)nums.size()); i++){
        dq.push_back(nums[i]);
        if(nums[i] > max_num) max_num = nums[i];
    }
    ret.push_back(max_num);
    for(int i=k; i<nums.size(); i++){
        if(nums[i] >= max_num){
            max_num = nums[i];
            dq.push_back(nums[i]);
            dq.pop_front();
        }else{
            dq.push_back(nums[i]);
            int cur = dq.front(); dq.pop_front();
            if(cur == max_num){
                max_num = INT_MIN;
                for(auto it : dq){
                    if(it > max_num) max_num = it;
                }
            }
        }
        ret.push_back(max_num);
    }
    return ret;
}