题目

数组num的长度为N，求其所有长度为W的连续区间的最大值。

一、平衡树

直接用map来对每个出现的值计数，map可以直接加入，删除，求最大。
时间复杂度O(NlogW)
空间复杂度O(N)

二、Sparse Table

利用Sparse_Table算法思想，将区间[A, A + W) 分解成[A, A+R) 和[A+W-R, A+W) 其中R是满足 2*R >= W的最小的2的次方。分解成的两个小区间有重叠，但由于是求最值，重叠部分不会影响答案。预处理部分中需要得到从每个下标A开始长度为1,2,4,8,...,R的区间的最值。相比Sparse_Table算法，这里的空间可以优化成O(N)，因为只需要保留长度为R的数组。
时间复杂度O(NlogW)
空间复杂度O(N)

三、单调队列

利用这条性质：当A < B且num[A] < num[B]时，num[A]对右端点在B或之后的区间来说可以忽略，因为num[B]是个更优解且num[A]先过期。
于是维护一个单调队列，队列中的元素由高到低排列（队列中存下标，方便判断过期）。
从小到大扫描num数组，当考虑到下标B时，根据上面的性质，可以安全地从队尾删除所有比num[B]小的值。
然后将B加入队尾。
然后从队首删除所有过期的值。
做完以上3点之后，队首的值即为以B为右端点的区间的最大值。
时间和空间复杂度都是O(N)，因为每个元素只进出一次队列。
时间复杂度O(N)
空间复杂度O(N)

四、代码

class Solution {
public:
    //平衡树
    vector<int> maxInWindows1(const vector<int>& num,int W)
    {
        int N = num.size();
        vector<int> ret;
        map<int, int> Count;

        for(int i = 0 ; i < N ; ++i){
            //加入当前值
            ++Count[num[i]];
            //删除过期元素
            if(i - W >= 0 && 0 == --Count[num[i - W]])
                Count.erase(num[i - W]);
            //计算答案
            if(i >= W - 1)
                ret.push_back(Count.rbegin()->first);
        }
        return ret;
    }
    //Sparse Table
    vector<int> maxInWindows2(const vector<int>& num,int W)
    {
        int N = num.size();

        vector<int> Max(num.begin(), num.end());
        int MaxRange = 1;
        //Max[i]为区间[i, i + MaxRange)中的最大值
        //每次循环将MaxRange翻倍并保持此性质

        while(MaxRange * 2 < W){
            for(int i = 0 ; i + 2 * MaxRange <= N ; ++i)
                Max[i] = max(Max[i], Max[i+MaxRange]);
            MaxRange *= 2;
        }
        //此时 MaxRange * 2 >= W，即MaxRange至少覆盖半个窗口

        vector<int> ret;
        for(int i = 0 ; i + W <= N; ++i){
            // [i, i + W)被分成[i, i + MaxRange)
            // 和 [i + W - MaxRange, i + W)这两个区间。
            ret.push_back(max(Max[i], Max[i+W-MaxRange]));
        }
        return ret;
    }
    //单调队列
    vector<int> maxInWindows3(const vector<int>& num, int W)
    {
        int N = num.size();

        vector<int> ret;
        list<int> L;
        for(int i = 0 ; i < N ; ++i){
            //从队尾删除比num[i]小的数
            while(!L.empty() && num[*L.rbegin()] < num[i])
                L.pop_back();

            //将i加入队尾
            L.push_back(i);

            //从队首删除过期的数
            while(!L.empty() && (*L.begin() <= i - W))
                L.pop_front();

            //将以i结尾的区间最值加入答案
            if(i >= W - 1)
                ret.push_back(num[*L.begin()]);
        }
        return ret;
    }
};