数据结构学习 jz59 滑动窗口的最大值

关键词：排序 大顶堆 双端队列

题目：?望远镜中最高的海拔

方法一：维护一个辅助队列。

方法二：大顶堆。

我还在主站 239 写了找最小值的方法。

方法一：最优解

这个方法和jz30维护一个非严格递减的辅助栈是基本一样的。

思路：

看了k神答案才懵懵懂懂会。建议看。

维护一个limit大小的双端队列作为辅助，这个双端队列存的是有可能成为最大值的潜在选手，如果在这个窗口内，后面的数大过了一些潜在选手，那么就把这些不够大的潜在选手淘汰（pop）。

我们需要一直保持这个双端的队列的非严格递减性。

可以将 “未形成窗口” 和 “形成窗口后” 两个阶段拆分到两个循环里实现。

复杂度计算：

时间复杂度O(n)

空间复杂度O(limit)

代码：

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        vector<int> result;
        if(heights.empty()||limit==0) return result;
        deque<int> dq;//双端非严格递减队列
        dq.push_back(heights[0]);//初始化第一个数
        //未形成窗口
        for(int i=1;i<limit;++i)
        {
            while(!dq.empty()&&heights[i]>dq.back()) 
            {
                dq.pop_back();
            }
            dq.push_back(heights[i]);
        }
        result.push_back(dq[0]);
        //形成窗口
        for(int i=limit;i<heights.size();++i)
        {
            //出栈最大值
            if(heights[i-limit]==dq[0])
            {
                dq.pop_front();
            }
            while(!dq.empty()&&heights[i]>dq.back())
            {
                dq.pop_back();
            }
            dq.push_back(heights[i]);
            result.push_back(dq[0]);
        }
        return result;
    }
};

方法二：

?大顶堆，优先序列。记录pair(val,index)，top的index如果超过了窗口左端，就推出。

思路：

这个方法很好理解，我刚开始也是希望用大顶堆做，但是没想到怎么删除已经超过窗口的数，这里给了我启发，只要记录一个pair(val,index)，就可以了。

在查询最大值的时候，同时检查index，如果超过了窗口的左端，那么就直接pop，直到找到窗口内的最大值。

复杂度计算：

时间复杂度O(nlogn)

空间复杂度O(n)

代码：

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        vector<int> result;
        if(heights.empty()||limit==0) return result;
        priority_queue<pair<int,int>> q;
        //未形成窗口前
        for(int i=0;i<limit;++i)
        {
            q.push({heights[i],i});
        }
        result.push_back(q.top().first);
        //形成窗口后
        for(int i=limit;i<heights.size();++i)
        {
            q.push({heights[i],i});
            while(q.top().second<=i-limit)
            {
                q.pop();
            }
            result.push_back(q.top().first);
        }
        return result;
    }
};