【一天一大 lee】有效的山脉数组 (难度:简单) - Day20201103
【一天一大 lee】有效的山脉数组 (难度:简单) - Day20201103
前端小书童
发布于 2020-11-04 15:27:19
发布于 2020-11-04 15:27:19
20201103
题目:
给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
A.length >= 3 在 0 < i < A.length - 1 条件下，存在 i 使得：
- A[0] < A[1] < ... A[i-1] < A[i]
- A[i] > A[i+1] > ... > A[A.length - 1]
有效的山脉数组
示例:
- 示例1:
输入：[2,1]
输出：false
- 示例2:
输入：[3,5,5]
输出：false
- 示例2:
输入：[0,3,2,1]
输出：true
提示:
- 0 <= A.length <= 10000
- 0 <= A[i] <= 10000
抛砖引玉
思路：
循环数组找到严格递增部分，当存在后一个值小于前一个值时判断是否严格递减，如果满足返回true，否则返回false
- 判断严格递增时索引不能在编辑上（0，A.length）
- 判断严格递减时需要遍历到数组结束
0 - 2 - 3 - 1
↑
开始判断递减
抛砖引玉
/**
* @param {number[]} A
* @return {boolean}
*/
var validMountainArray = function(A) {
let len = A.length,
index = 0,
maxIndex = 1
if(len < 3) return false
// 递增
while(A[index] < A[maxIndex] && maxIndex < len){
index++
maxIndex++
}
// 判断递增范围是否满足条件
if(index == 0 || index == len - 1) return false
// 递减
while(A[maxIndex] < A[index] && index < len){
index++
maxIndex++
}
return index === len -1
};
上面通过index和maxIndex区分前后两个数，其实完全可以通过一个索引完成：
简化
var validMountainArray = function(A) {
let len = A.length,
index = 0
if(len < 3) return false
// 递增
while(A[index] < A[index+1] && index+1 < len){
index++
}
// 判断递增范围是否满足条件
if(index == 0 || index == len - 1) return false
// 递减
while(A[index+1] < A[index] && index < len){
index++
}
return index === len -1
};
双指针
通过双指针：start、end分别从数组的前后递增(start)、递减(end)，检查指针最后是否能重叠
- start和end如果完成递增、递减逻辑后仍处在边界上说明不存在满足条件的递增、递减区间
- start和end最后不能重叠则说明存在不满足条件区间
var validMountainArray = function(A) {
let len = A.length,
start = 0,
end = len-1
if(len < 3) return false
// 从0开始遍历递增区间
while(A[start] < A[start+1] && start+1 < len){
start++
}
// 从数组末尾开始遍历递减区间
while(A[end] < A[end-1] && end-1 >= 0){
end--
}
// 判断是否存在递增、递减区间及双指针是否重叠
return start != 0 && start == end && end != len - 1
};
博客: 前端小书童
每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号：前端小书童
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-11-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录