leetcode
leetcode 851 ~ 900
有效的山脉数组

有效的山脉数组

难度:

标签:

题目描述

给定一个整数数组 arr,如果它是有效的山脉数组就返回 true,否则返回 false

让我们回顾一下,如果 arr 满足下述条件,那么它是一个山脉数组:

  • arr.length >= 3
  • 在 0 < i < arr.length - 1 条件下,存在 i 使得:
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

 

 

示例 1:

输入:arr = [2,1]
输出:false

示例 2:

输入:arr = [3,5,5]
输出:false

示例 3:

输入:arr = [0,3,2,1]
输出:true

 

提示:

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 104

代码结果

运行时间: 26 ms, 内存: 17.0 MB


// 思路:
// 1. 使用Stream API处理数组,先检查数组长度是否大于等于3。
// 2. 使用filter找到满足条件的峰值索引。
// 3. 使用IntStream进行递增递减检查。
// 4. 如果条件都满足,返回true。

import java.util.stream.IntStream;

public class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        if (n < 3) return false;

        int peakIndex = IntStream.range(1, n - 1)
            .filter(i -> arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
            .findFirst()
            .orElse(-1);

        if (peakIndex == -1) return false;

        boolean increasing = IntStream.range(0, peakIndex).allMatch(i -> arr[i] < arr[i + 1]);
        boolean decreasing = IntStream.range(peakIndex, n - 1).allMatch(i -> arr[i] > arr[i + 1]);

        return increasing && decreasing;
    }
}

解释

方法:

解题思路是模拟爬山的过程。首先检查数组长度是否小于3,或者数组的第二个元素小于等于第一个元素,或者数组的最后一个元素大于等于倒数第二个元素的情况,这些情况都直接返回false。然后使用一个变量peak来标记是否已经达到山顶。遍历数组,如果当前元素等于前一个元素,返回false,因为山脉数组中元素必须严格递增或递减。如果未达到山顶且当前元素小于前一个元素,则标记已达到山顶。如果已达到山顶但当前元素大于前一个元素,则返回false。如果成功遍历完成,则返回true。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么初始条件中需要验证`arr[1] <= arr[0]`和`arr[-1] >= arr[-2]`? 这两个条件分别代表了什么意义?
这两个条件用于确保数组可以形成一个山脉的形状。`arr[1] <= arr[0]`条件排除了数组开头是下坡或平坦的情况,因为一个有效的山脉数组必须从低处开始上升。相似地,`arr[-1] >= arr[-2]`条件排除了数组结尾是上升或平坦的情况,确保山脉在达到顶峰后必须下降。这两个条件是为了确保数组开始时上升并在结束前下降,符合山脉的基本形态。
🦆
在代码中,`peak`变量是如何确保只标记一次山顶的?如果数组中有多个峰值怎么处理?
代码中,`peak`变量在初始设置为`False`,表示山顶未被到达。当检测到第一次元素从上升转为下降时(即`num < pre`),`peak`会被设置为`True`,代表已经到达山顶。此后,`peak`不会被重新设置,这确保了山顶只被标记一次。如果数组中存在多个上升后再下降的序列,即存在多个峰值,那么在第二次尝试上升(即遇到`num > pre`且`peak`已为`True`)时,代码将返回`False`,因为有效的山脉数组中只能有一个顶峰。
🦆
在遍历过程中,如果`arr[i]`小于`arr[i-1]`后直接设置`peak`为`True`,是否考虑了可能存在的多段递减序列?
代码的逻辑确实考虑了只有单段递减的情况。在`peak`被设置为`True`后,任何后续的上升(`num > pre`)都会触发函数返回`False`。这意味着,如果存在多段递减序列(即在下降后再次上升再下降),代码将正确地判断这不是一个有效的山脉数组。因此,一旦开始下降,再次上升将被视为不符合山脉数组的条件。
🦆
为什么在检测到`peak`后,如果出现`num > pre`则直接返回`False`,这里是否有考虑到可能的输入误差或特殊情况?
在该算法中,一旦`peak`被设置(即已经到达山顶并开始下降),任何后续的`num > pre`(即再次上升)都会导致返回`False`。这种设计是基于题目要求,即山脉数组在到达峰顶后必须严格递减,不存在再次上升的情况。因此,这里没有考虑输入误差或特殊情况,如微小的波动或数据错误,算法严格遵守题目的定义。

相关问题