数组中的最长山脉
难度:
标签:
题目描述
代码结果
运行时间: 35 ms, 内存: 16.9 MB
/*
* 题目思路:
* 通过Java Stream API解决问题,我们可以使用IntStream来遍历数组,
* 通过条件过滤找到每个山脉的峰顶,并计算每个山脉的长度。
*/
import java.util.stream.IntStream;
public int longestMountainStream(int[] arr) {
int n = arr.length;
if (n < 3) return 0;
return IntStream.range(1, n - 1)
.filter(i -> arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
.map(i -> {
int left = i, right = i;
while (left > 0 && arr[left] > arr[left - 1]) left--;
while (right < n - 1 && arr[right] > arr[right + 1]) right++;
return right - left + 1;
})
.max()
.orElse(0);
}
解释
方法:
该题解采用单遍扫描数组的方式来识别并计算最长的山脉子数组的长度。从数组的第二个元素开始,直到倒数第二个元素结束,判断每个元素是否是山脉的峰顶(即当前元素比左右两边的元素都要大)。若是,则分别向左和向右扩展,直到不满足上升或下降的条件,从而确定整个山脉的边界。最后,计算当前山脉的长度,并与已记录的最长长度进行比较,更新最长长度。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中,你是如何确定只需从第二个元素开始检查直到倒数第二个元素结束,而不需要检查数组的第一个或最后一个元素是否为山峰的?
▷🦆
该算法在发现当前元素是山峰时才开始向左右扩展,这种方法是否可能错过某些较短的山脉子数组,或者说是否有可能漏掉某些特殊情况?
▷🦆
对于连续相等的元素,例如数组中包含 [3, 3, 3] 这样的部分,这种情况下算法是如何处理的?会不会影响山脉的判断?
▷🦆
在向左和向右扩展时,为什么要求 `left > 0` 和 `right < size - 1`?这些条件的边界设置有什么特别的意义吗?
▷