望远镜中最高的海拔
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 452 ms, 内存: 18.2 MB
/*
思路:使用Java Stream API无法直接实现复杂的滑动窗口操作,因此需要将滑动窗口逻辑分解为可用的Stream操作。
1. 生成滑动窗口的起始索引。
2. 对每个起始索引,生成相应的窗口并计算最大值。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int[] maxSlidingWindow(int[] heights, int limit) {
if (heights == null || heights.length == 0) return new int[0];
return IntStream.range(0, heights.length - limit + 1)
.map(i -> Arrays.stream(heights, i, i + limit).max().getAsInt())
.toArray();
}
}
解释
方法:
本题解采用了单调队列的数据结构来解决滑动窗口中的最大值问题。整体思路是维护一个单调递减的队列,队列中存储的是数组索引,确保队列的队首始终是当前滑动窗口的最大值的索引。对于每个元素,首先判断队首元素是否超出了当前滑动窗口的范围,如果超出则将其从队首移除。之后,从队尾开始,移除所有小于或等于当前元素的索引,以维持队列的单调递减性。最后将当前元素的索引加入队尾。如果已经遍历的元素数量达到窗口大小,则将队首对应的元素值加入结果数组。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在单调队列中,为什么选择保持队列的单调递减而不是单调递增?
▷🦆
如果`limit`大于数组`heights`的长度,该算法是否还能正确返回结果,需要怎样的调整?
▷🦆
在单调队列的实现中,移除队首元素的条件为`i - q[0] + 1 > limit`,请问为什么这里使用`+1`进行计算?
▷