題目描述

給定一個整數(shù)數(shù)組 A，如果它是有效的山脈數(shù)組就返回 true，否則返回 false。

讓我們回顧一下，如果 A 滿足下述條件，那么它是一個山脈數(shù)組：

• 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> 如題目所描述，山脈數(shù)組A需滿足條件：A.length >= 3

<2> 如下圖所示的兩種情況，都不符合山脈數(shù)組，即左右指針不能在數(shù)組索引0處和A.length - 1處相遇

左右指針在A數(shù)組索引0處相遇.png

左右指針在A數(shù)組索引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> 首先我們得找到山頂：從左向右開始遍歷數(shù)組A，直到第一個出現(xiàn)A[i+1] < A[i]時，則i就是數(shù)組的最高點(diǎn)(山頂)的下標(biāo)。

<2> 從山頂下標(biāo)i開始繼續(xù)向右遍歷，并判斷數(shù)組A是否都滿足A[i+1] > A[i]，都滿足則返回true，否則返回false。

邊界檢查： 山脈數(shù)組的山頂不能在數(shù)組的第一個位置(0)和最后一個位置(A.length-1)，因此我們第一步找到的山頂下標(biāo)為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++;
        }
        // 山頂不能位于數(shù)組的第一個位置和最后一個位置
        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++;
        }
        // 山頂不能位于數(shù)組的第一個位置和最后一個位置
        if (i == 0 || i == n-1) {
            return false;
        }
        // 判斷剩余數(shù)組元素是否都為遞減
        for (int j = i; j+1 < n; j++) {
            if (A[j+1] >= A[j]) {
                return false;
            }
        }
        return true;
    }
}

思路三：狀態(tài)切換法 - 上山下山，切換狀態(tài)

<1> 初始status = 1，表示上山，并從左向右遍歷數(shù)組A，當(dāng)出現(xiàn)第一個A[i+1] < A[i]時，則到達(dá)山頂，山頂下標(biāo)為i，然后切換狀態(tài)：status = 2，開始下山。

<2> 處于下山狀態(tài)(status = 2)時，從山頂下標(biāo)i開始，數(shù)組都滿足A[i+1] < A[i]，則為山脈數(shù)組，返回true，否則返回false。

邊界檢查： 山脈數(shù)組的山頂不能在數(shù)組的第一個位置(0)和最后一個位置(A.length-1)，即都不可能切換為下山狀態(tài)(status = 2)，最終我們判斷一下status == 2即可。

狀態(tài)切換法 - 上山下山，切換狀態(tài).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;
                }
            }
        }
        // 單調(diào)遞增，單調(diào)遞減，最終狀態(tài)都不為下山狀態(tài)(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;
            }
        }
        // 單調(diào)遞增，單調(diào)遞減，最終狀態(tài)都不為下山狀態(tài)(status = 2)
        return status == 2;
    }
}