单调队列

 1class Solution {
 2public:
 3    vector<int> maxAltitude(vector<int> &heights, int limit)
 4    {
 5        int n = heights.size();
 6        deque<int> dq;
 7        vector<int> ans;
 8
 9        for (int i = 0; i < n; ++i) {
10            // 维护长度
11            while (!dq.empty() && dq.front() <= i - limit) {
12                dq.pop_front();
13            }
14
15            // 维护单调性
16            while (!dq.empty() && heights[dq.back()] <= heights[i]) {
17                dq.pop_back();
18            }
19            dq.push_back(i);
20
21            // 滑动窗口长度时，记录最大值
22            if (i >= limit - 1) {
23                ans.push_back(heights[dq.front()]);
24            }
25        }
26        return ans;
27    }
28};