有效的山脉数组
难度:
标签:
题目描述
给定一个整数数组 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]`? 这两个条件分别代表了什么意义?
▷🦆
在代码中,`peak`变量是如何确保只标记一次山顶的?如果数组中有多个峰值怎么处理?
▷🦆
在遍历过程中,如果`arr[i]`小于`arr[i-1]`后直接设置`peak`为`True`,是否考虑了可能存在的多段递减序列?
▷🦆
为什么在检测到`peak`后,如果出现`num > pre`则直接返回`False`,这里是否有考虑到可能的输入误差或特殊情况?
▷