本文主要是介绍数据结构学习 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;}
};这篇关于数据结构学习 jz59 滑动窗口的最大值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
