自律小屋解题思路：
设窗口区间为 $[i, j]$ ，最大值为 $x_j$ 。当窗口向前移动一格，则区间变为 $[i+1,j+1]$ ，即添加了 $heights[j + 1]$ ，删除了 $heights[i]$ 。
若只向窗口 $[i, j]$ 右边添加数字 $heights[j + 1]$ ，则新窗口最大值可以 通过一次对比 使用 $O(1)$ 时间得到，即：
$$ x_{j+1} = \max(x_{j}, heights[j + 1]) $$
而由于删除的 $heights[i]$ 可能恰好是窗口内唯一的最大值 $x_j$ ，因此不能通过以上方法计算 $x_{j+1}$ ，而必须使用 $O(j-i)$ 时间， 遍历整个窗口区间 获取最大值，即：
$$ x_{j+1} = \max(heights(i+1), \cdots , heights(j+1)) $$
根据以上分析，可得 暴力法 的时间复杂度为 $O((n-limit+1)limit) \approx O(nk)$ 。
- 设数组 $heights$ 的长度为 $n$ ，则共有 $(n-limit+1)$ 个窗口；
- 获取每个窗口最大值需线性遍历，时间复杂度为 $O(limit)$ 。
下图中的
nums对应本题的heights。
本题难点： 如何在每次窗口滑动后，将 “获取窗口内最大值” 的时间复杂度从 $O(limit)$ 降低至 $O(1)$ 。
回忆“最小栈”问题，其使用 单调栈 实现了随意入栈、出栈情况下的 $O(1)$ 时间获取 “栈内最小值” 。本题同理，不同点在于 “出栈操作” 删除的是 “列表尾部元素” ，而 “窗口滑动” 删除的是 “列表首部元素” 。
窗口对应的数据结构为 双端队列 ，本题使用 单调队列 即可解决以上问题。遍历数组时，每轮保证单调队列 $deque$ ：
- $deque$ 内 仅包含窗口内的元素 $\Rightarrow$ 每轮窗口滑动移除了元素 $heights[i - 1]$ ，需将 $deque$ 内的对应元素一起删除。
- $deque$ 内的元素 非严格递减 $\Rightarrow$ 每轮窗口滑动添加了元素 $heights[j + 1]$ ，需将 $deque$ 内所有 $< heights[j + 1]$ 的元素删除。
算法流程：
- 初始化： 双端队列 $deque$ ，结果列表 $res$ ，数组长度 $n$ ；
- 滑动窗口： 左边界范围 $i \in [1 - limit, n - limit]$ ，右边界范围 $j \in [0, n - 1]$ ；
- 若 $i > 0$ 且 队首元素 $deque[0]$ $=$ 被删除元素 $heights[i - 1]$ ：则队首元素出队；
- 删除 $deque$ 内所有 $< heights[j]$ 的元素，以保持 $deque$ 递减；
- 将 $heights[j]$ 添加至 $deque$ 尾部；
- 若已形成窗口（即 $i \geq 0$ ）：将窗口最大值（即队首元素 $deque[0]$ ）添加至列表 $res$ ；
- 返回值： 返回结果列表 $res$ ；
<
,
,
,
,
,
,
,
,
,
>
代码：
Python 通过 zip(range(), range()) 可实现滑动窗口的左右边界 i, j 同时遍历。
class Solution:
def maxAltitude(self, heights: List[int], limit: int) -> List[int]:
deque = collections.deque()
res, n = [], len(heights)
for i, j in zip(range(1 - limit, n + 1 - limit), range(n)):
# 删除 deque 中对应的 heights[i-1]
if i > 0 and deque[0] == heights[i - 1]:
deque.popleft()
# 保持 deque 递减
while deque and deque[-1] < heights[j]:
deque.pop()
deque.append(heights[j])
# 记录窗口最大值
if i >= 0:
res.append(deque[0])
return resclass Solution {
public int[] maxAltitude(int[] heights, int limit) {
if(heights.length == 0 || limit == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[heights.length - limit + 1];
for(int j = 0, i = 1 - limit; j < heights.length; i++, j++) {
// 删除 deque 中对应的 heights[i-1]
if(i > 0 && deque.peekFirst() == heights[i - 1])
deque.removeFirst();
// 保持 deque 递减
while(!deque.isEmpty() && deque.peekLast() < heights[j])
deque.removeLast();
deque.addLast(heights[j]);
// 记录窗口最大值
if(i >= 0)
res[i] = deque.peekFirst();
}
return res;
}
}可以将 “未形成窗口” 和 “形成窗口后” 两个阶段拆分到两个循环里实现。代码虽变长，但减少了冗余的判断操作。
class Solution:
def maxAltitude(self, heights: List[int], limit: int) -> List[int]:
if not heights or limit == 0: return []
deque = collections.deque()
# 未形成窗口
for i in range(limit):
while deque and deque[-1] < heights[i]:
deque.pop()
deque.append(heights[i])
res = [deque[0]]
# 形成窗口后
for i in range(limit, len(heights)):
if deque[0] == heights[i - limit]:
deque.popleft()
while deque and deque[-1] < heights[i]:
deque.pop()
deque.append(heights[i])
res.append(deque[0])
return resclass Solution {
public int[] maxAltitude(int[] heights, int limit) {
if(heights.length == 0 || limit == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[heights.length - limit + 1];
// 未形成窗口
for(int i = 0; i < limit; i++) {
while(!deque.isEmpty() && deque.peekLast() < heights[i])
deque.removeLast();
deque.addLast(heights[i]);
}
res[0] = deque.peekFirst();
// 形成窗口后
for(int i = limit; i < heights.length; i++) {
if(deque.peekFirst() == heights[i - limit])
deque.removeFirst();
while(!deque.isEmpty() && deque.peekLast() < heights[i])
deque.removeLast();
deque.addLast(heights[i]);
res[i - limit + 1] = deque.peekFirst();
}
return res;
}
}复杂度分析：
- 时间复杂度 $O(n)$ ： 其中 $n$ 为数组 $heights$ 长度；线性遍历 $heights$ 占用 $O(n)$ ；每个元素最多仅入队和出队一次，因此单调队列 $deque$ 占用 $O(2n)$ 。
- 空间复杂度 $O(limit)$ ： 双端队列 $deque$ 中最多同时存储 $limit$ 个元素（即窗口大小）。