一、题目
给定一个整数数组 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
二、思路
第一时间想到的是先找到数字的最大值的下标也就是山峰的位置,再分别判断左半和右半是否是严格递增和递减的。不过要注意数组单调的话也不是山脉数组。
然后再想有没有别的方法更高效,看了大佬的思路发现可以用相向指针解决。
三、代码
遍历法:
class Solution {public boolean validMountainArray(int[] arr) {if(arr.length < 3) {return false;}//先找到数字的最大值的下标也就是山峰的位置int max = 0;int index = 0;for(int i = 0;i< arr.length;i++) {if(arr[i] > max) {max = arr[i];index = i;}}//单调的话也不是山峰if(index == arr.length - 1 || index == 0) {return false;}//再分别判断左半和右半是否是严格递增和递减的。for(int j = 0;j < index;j++) {if(arr[j] >= arr[j+1]) {return false;}}for(int j = index;j<arr.length - 1;j++) {if(arr[j] <= arr[j+1]) {return false;}}return true;}
}
双指针法:
class Solution {public boolean validMountainArray(int[] arr) {if (arr.length < 3) { // 此时,一定不是有效的山脉数组return false;}// 双指针int left = 0;int right = arr.length - 1;// 注意防止指针越界while (left + 1 < arr.length && arr[left] < arr[left + 1]) {left++;}// 注意防止指针越界while (right > 0 && arr[right] < arr[right - 1]) {right--;}// 如果left或者right都在起始位置,说明不是山峰if (left == right && left != 0 && right != arr.length - 1) {return true;}return false;}
}