望远镜中最高的海拔

难度: Hard

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

注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/

Submission

运行时间: 452 ms

内存: 18.2 MB

class Solution:
    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:

        q = deque()
        res = []
        for i, x in enumerate(heights):
            while q and i - q[0] + 1 > limit:
                q.popleft()
            while q and heights[q[-1]] <= x:
                q.pop()
            q.append(i)
            if i + 1 >= limit:
                res.append(heights[q[0]])
        return res

Explain

本题解采用了单调队列的数据结构来解决滑动窗口中的最大值问题。整体思路是维护一个单调递减的队列，队列中存储的是数组索引，确保队列的队首始终是当前滑动窗口的最大值的索引。对于每个元素，首先判断队首元素是否超出了当前滑动窗口的范围，如果超出则将其从队首移除。之后，从队尾开始，移除所有小于或等于当前元素的索引，以维持队列的单调递减性。最后将当前元素的索引加入队尾。如果已经遍历的元素数量达到窗口大小，则将队首对应的元素值加入结果数组。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:
        q = deque()  # 初始化双端队列
        res = []  # 初始化结果列表
        for i, x in enumerate(heights):  # 遍历高度列表
            while q and i - q[0] + 1 > limit:  # 移除超出滑动窗口范围的队首元素
                q.popleft()
            while q and heights[q[-1]] <= x:  # 维持队列的单调递减
                q.pop()
            q.append(i)  # 将当前元素索引加入队列
            if i + 1 >= limit:  # 当窗口大小达到limit时，记录结果
                res.append(heights[q[0]])  # 队首元素即为当前窗口的最大值
        return res

Explore

在这个问题中，我们需要在每个滑动窗口中快速获取最大值。如果维持一个单调递减的队列，队首元素就是窗口中的最大值。这样，每次窗口滑动时，只需检查队首元素即可直接得到最大值，从而保证了操作的高效性。如果队列是单调递增的，则需要遍历整个队列来找到最大值，这将增加计算的复杂性和时间消耗。

如果`limit`大于`heights`的长度，整个数组都在一个滑动窗口中。在这种情况下，算法应该返回整个数组中的最大值。为了适应这种情况，可以在算法开始时添加一个判断：如果`limit`大于或等于`heights`长度，直接找出并返回`heights`中的最大值，而无需执行滑动窗口的逻辑。

这里使用`+1`是为了将索引间的距离转换为元素数量。在数组中，`i`和`q[0]`分别是当前元素和队首元素的索引。索引差`i - q[0]`实际上表示的是两者之间的间隔数量。为了得到包括两端在内的元素总数，需要加1。因此，`i - q[0] + 1`表示的是从队首到当前元素包含的元素总数。当这个数大于`limit`时，说明队首元素已不在当前滑动窗口范围内，需要被移除。