leetcode
leetcode 751 ~ 800
数组中的最长山脉

数组中的最长山脉

难度:

标签:

题目描述

代码结果

运行时间: 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`?这些条件的边界设置有什么特别的意义吗?
在向左和向右扩展时,条件 `left > 0` 和 `right < size - 1` 确保了数组索引不会越界。向左扩展时,必须确保 `left` 位于数组的有效索引范围内(即大于0),这样才能安全地访问 `arr[left - 1]`;同理,向右扩展时,`right` 必须小于数组的最大索引(即 `size - 1`),以便安全地访问 `arr[right + 1]`。这些边界条件是为了保证程序不会因为数组越界而发生错误。

相关问题