题目描述
给定一个整数数组 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]
图片来源力扣.png
示例 1：
输入：[2,1]
输出：false
示例 2：
输入：[3,5,5]
输出：false
示例 3：
输入：[0,3,2,1]
输出：true
提示：
0 <= A.length <= 10000
0 <= A[i] <= 10000
力扣（LeetCode）题目链接地址：https://leetcode-cn.com/problems/valid-mountain-array/
思路解析
思路一：双指针 - 左右爬山法
拿到题目，首先想到的就是利用双指针，从左右分别爬山，最后在山顶相遇，如下图所示：
双指针-左右爬山法.png
边界值处理：
<1> 如题目所描述，山脉数组A需满足条件：A.length >= 3
<2> 如下图所示的两种情况，都不符合山脉数组，即左右指针不能在数组索引0处和A.length - 1处相遇
左右指针在A数组索引0处相遇.png
左右指针在A数组索引A.length-1处相遇.png
最初版本一：
class Solution {
public boolean validMountainArray(int[] A) {
int n = A.length;
if (n < 3 || A[0] >= A[1] || A[n-2] <= A[n-1]) { // 边界检查也可以不加
return false;
}
int i;
for (i = 0; i+1 < n; i++) {
if (A[i+1] == A[i]) {
return false;
}
if (A[i+1] < A[i]) {
break;
}
}
int j;
for (j = n - 1; j-1 >= 0; j--) {
if (A[j-1] == A[j]) {
return false;
}
if (A[j-1] < A[j]) {
break;
}
}
return i != 0 && j != n-1 && i == j;
}
}
简化版本二：
class Solution {
public boolean validMountainArray(int[] A) {
int n = A.length;
if (n < 3 || A[0] >= A[1] || A[n-2] <= A[n-1]) { // 边界检查也可以不加
return false;
}
int i = 0;
while(i+1 < n && A[i+1] > A[i]) {
i++;
}
int j = n - 1;
while (j-1 >=0 && A[j-1] > A[j]) {
j--;
}
return i != 0 && j != n-1 && i == j;
}
}
思路二：线性扫描 - 爬上山顶，一路向下
<1> 首先我们得找到山顶：从左向右开始遍历数组A，直到第一个出现A[i+1] < A[i]时，则i就是数组的最高点(山顶)的下标。
<2> 从山顶下标i开始继续向右遍历，并判断数组A是否都满足A[i+1] > A[i]，都满足则返回true，否则返回false。
边界检查： 山脉数组的山顶不能在数组的第一个位置(0)和最后一个位置(A.length-1)，因此我们第一步找到的山顶下标为0或A.length-1时，直接返回false。
线性扫描 - 爬上山顶，一路向下.png
class Solution {
public boolean validMountainArray(int[] A) {
int n = A.length;
if (n < 3 || A[0] >= A[1] || A[n-2] <= A[n-1]) { // 边界检查也可以不加
return false;
}
int i = 0;
// 递增扫描，找到山顶
while (i+1 < n && A[i+1] > A[i]) {
i++;
}
// 山顶不能位于数组的第一个位置和最后一个位置
if (i == 0 || i == n-1) {
return false;
}
// 递减扫描
while (i+1 < n && A[i+1] < A[i]) {
i++;
}
return i == n-1;
}
}
另一版本：
class Solution {
public boolean validMountainArray(int[] A) {
int n = A.length;
if (n < 3 || A[0] >= A[1] || A[n-2] <= A[n-1]) { // 边界检查也可以不加
return false;
}
int i = 0;
// 递增扫描，找到山顶
while (i+1 < n && A[i+1] > A[i]) {
i++;
}
// 山顶不能位于数组的第一个位置和最后一个位置
if (i == 0 || i == n-1) {
return false;
}
// 判断剩余数组元素是否都为递减
for (int j = i; j+1 < n; j++) {
if (A[j+1] >= A[j]) {
return false;
}
}
return true;
}
}
思路三：状态切换法 - 上山下山，切换状态
<1> 初始status = 1，表示上山，并从左向右遍历数组A，当出现第一个A[i+1] < A[i]时，则到达山顶，山顶下标为i，然后切换状态：status = 2，开始下山。
<2> 处于下山状态(status = 2)时，从山顶下标i开始，数组都满足A[i+1] < A[i]，则为山脉数组，返回true，否则返回false。
边界检查： 山脉数组的山顶不能在数组的第一个位置(0)和最后一个位置(A.length-1)，即都不可能切换为下山状态(status = 2)，最终我们判断一下status == 2即可。
状态切换法 - 上山下山，切换状态.png
switch 版本：
class Solution {
public boolean validMountainArray(int[] A) {
int n = A.length;
if (n < 3 || A[0] >= A[1] || A[n-2] <= A[n-1]) { // 边界检查也可以不加
return false;
}
int status = 1;
for (int i = 0; i+1 < n; i++) {
switch(status) {
case 1: {
if (A[i+1] < A[i]) {
status = 2;
}
break;
}
case 2: {
if (A[i+1] >= A[i]) {
return false;
}
break;
}
}
}
// 单调递增，单调递减，最终状态都不为下山状态(status = 2)
return status == 2;
}
}
if 版本：
class Solution {
public boolean validMountainArray(int[] A) {
int n = A.length;
if (n < 3 || A[0] >= A[1] || A[n-2] <= A[n-1]) { // 边界检查也可以不加
return false;
}
int status = 1;
for (int i = 0; i+1 < n; i++) {
if (status == 1 && A[i+1] < A[i]) {
status = 2;
}
if (status == 2 && A[i+1] >= A[i]) {
return false;
}
}
// 单调递增，单调递减，最终状态都不为下山状态(status = 2)
return status == 2;
}
}
网友评论