leetcode
leetcode 2601 ~ 2650
望远镜中最高的海拔

望远镜中最高的海拔

难度:

标签:

题目描述

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`的长度,该算法是否还能正确返回结果,需要怎样的调整?
如果`limit`大于`heights`的长度,整个数组都在一个滑动窗口中。在这种情况下,算法应该返回整个数组中的最大值。为了适应这种情况,可以在算法开始时添加一个判断:如果`limit`大于或等于`heights`长度,直接找出并返回`heights`中的最大值,而无需执行滑动窗口的逻辑。
🦆
在单调队列的实现中,移除队首元素的条件为`i - q[0] + 1 > limit`,请问为什么这里使用`+1`进行计算?
这里使用`+1`是为了将索引间的距离转换为元素数量。在数组中,`i`和`q[0]`分别是当前元素和队首元素的索引。索引差`i - q[0]`实际上表示的是两者之间的间隔数量。为了得到包括两端在内的元素总数,需要加1。因此,`i - q[0] + 1`表示的是从队首到当前元素包含的元素总数。当这个数大于`limit`时,说明队首元素已不在当前滑动窗口范围内,需要被移除。

相关问题