科技馆内有一台虚拟观景望远镜，它可以用来观测特定纬度地区的地形情况。该纬度的海拔数据记于数组 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

此题目的是寻找每个limit中的最大值，想到可以使用优先队列维护每一个limit中最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> maxAltitude(vector<int> &heights, int limit) {
        if (heights.empty())
            return {};
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < limit; i++) {
            pq.emplace(heights[i], i);
        }
        vector<int> ans = {pq.top().first};
        for (int i = limit; i < heights.size(); i++) {
            pq.emplace(heights[i], i); // 放在while后面会超时
            // 先入队可以时合法索引范围变大---删除的元素就少些
            while (i - limit >= pq.top().second)
                pq.pop();
            ans.push_back(pq.top().first);
        }
        return ans;
    }
};

注意到队列只有在最大值脱离窗口时才需要更新

窗口中，如果先出现的元素比后出现的元素小，因为窗口是往右移动的，那么先出现的元素一定不会成为最大值，可以考虑使用单调队列

维护一个单调递减的队列，后出现的元素如果比先前某个元素还大则不再考虑先前的此元素

在最大值脱离窗口时才弹出队首

并且使用值来判断最大值是否脱离窗口

相等时先出现的元素其实不会成为最大值，但是因为直接根据值来判断最大值是否脱离，所以相等时相当于有多个最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> maxAltitude(vector<int> &heights, int limit) {
        if (heights.empty())
            return {};
        deque<int> dq;
        for (int i = 0; i < limit; i++) {
            while (!dq.empty() && heights[i] > dq.back())
                dq.pop_back();
            dq.push_back(heights[i]);
        }
        vector<int> ans = {dq.front()};
        for (int i = limit; i < heights.size(); i++) {
            if (dq.front() == heights[i - limit])
                dq.pop_front();
            while (!dq.empty() && heights[i] > dq.back())
                dq.pop_back();
            dq.push_back(heights[i]);
            ans.push_back(dq.front());
        }
        return ans;
    }
};