科技馆内有一台虚拟观景望远镜,它可以用来观测特定纬度地区的地形情况。该纬度的海拔数据记于数组 heights
,其中 heights[i]
表示对应位置的海拔高度。请找出并返回望远镜视野范围 limit
内,可以观测到的最高海拔值。
示例 1:
输入:heights = [14,2,27,-5,28,13,39], limit = 3 输出:[27,27,28,28,39] 解释: 滑动窗口的位置 最大值 --------------- ----- [14 2 27] -5 28 13 39 27 14 [2 27 -5] 28 13 39 27 14 2 [27 -5 28] 13 39 28 14 2 27 [-5 28 13] 39 28 14 2 27 -5 [28 13 39] 39
提示:
你可以假设输入总是有效的,在输入数组不为空的情况下:
1 <= limit <= heights.length
-10000 <= heights[i] <= 10000
思路:
1、利用双端队列,但需要注意的是保存的是数组元素的下标。保证当前队列为单调递减队列。有以下几种情况。
2、需要保证窗口的大小不能超过limit,即当前元素下标减去队首元素(存放的是元素下标)是否超过limit,超过则让队首元素出队,进行下一步。
3、需要保证队列为递减的,因此每次末尾入队时出队所有小于他的元素(下标)。
4、若下标已经开始超过滑动窗口的限制,此时就需要向结果数组中插入每一次滑动窗口中的最大值,也就是以队首元素为下标的数组值。
代码实现:
class Solution {
public:
vector<int> maxAltitude(vector<int>& heights, int limit) {
int size = heights.size();
vector<int>res;
for(int i = 0; i < size; i++)
{
while(!q.empty() && i - q.front() > limit - 1) //滑动窗口大小不能超过limit
q.pop_front();
while(!q.empty() && heights[i] >= heights[q.back()]) //保证队列递减,队首始终保存滑动窗口最大值的下标
q.pop_back();
q.push_back(i);
if(i >= limit - 1) //从超过滑动窗口的大小开始就需要向结果数组中插入每一次的最大值
res.push_back(heights[q.front()]);
}
return res;
}
private:
deque<int>q;
};
标签:39,27,LCR,双端,28,13,heights,183,limit
From: https://blog.csdn.net/m0_72855061/article/details/136655337