❓941. 有效的山脉数组
难度：简单
给定一个整数数组 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
<
=
a
r
r
.
l
e
n
g
t
h
<
=
1
0
4
1 <= arr.length <= 10^4
1<=arr.length<=104
0
<
=
a
r
r
[
i
]
<
=
1
0
4
0 <= arr[i] <= 10^4
0<=arr[i]<=104
思路：双指针
判断是山峰，主要就是要严格的保存左边到中间递增的，及右边到中间是递增的。
这样可以使用两个指针，left 和 right。因为 left 和 right 是数组下标，移动的过程中注意不要数组越界；如果 left 或者 right 没有移动，说明是一个单调递增或者递减的数组，依然不是山峰。
代码：(Java、C++)
Java
class Solution {
public boolean validMountainArray(int[] arr) {
int n = arr.length;
if (n < 3) return false;
int left = 0;
int right = n - 1;
// 严格递增遍历，注意防止越界
while (left < n - 1 && arr[left] < arr[left + 1]) left++;
// 严格递减遍历，注意防止越界
while (right > 0 && arr[right] < arr[right - 1]) right--;
// 如果left或者right都在起始位置，说明不是山峰
if (left == right && left != 0 && right != n - 1) return true;
return false;
}
}
C++
class Solution {
public:
bool validMountainArray(vector
int n = arr.size();
if (n < 3) return false;
int left = 0;
int right = n - 1;
// 严格递增遍历，注意防止越界
while (left < n - 1 && arr[left] < arr[left + 1]) left++;
// 严格递减遍历，注意防止越界
while (right > 0 && arr[right] < arr[right - 1]) right--;
// 如果left或者right都在起始位置，说明不是山峰
if (left == right && left != 0 && right != n - 1) return true;
return false;
}
};
运行结果：
复杂度分析：
时间复杂度：
O
(
n
)
O(n)
O(n)，其中 n 为数组 arr 的长度。空间复杂度：
O
(
1
)
O(1)
O(1)。
题目来源：力扣。
放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！ 关注我LeetCode主页 / CSDN—力扣专栏，每日更新！
注： 如有不足，欢迎指正！
精彩链接
您阅读本篇文章共花了：
发表评论