如果 A 滿(mǎn)足下述條件，那么它是一個(gè)山脈數(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]

我的解法：
1胸囱、定義left、right變量記錄首次打破遞增的位置瀑梗；
2烹笔、從左到右計(jì)算left、從右到左計(jì)算right抛丽；
3谤职、判斷l(xiāng)eft+right是否等于A.length-1；
時(shí)間復(fù)雜度：O(n)亿鲜，空間復(fù)雜度：O(1)

class Solution {
    public boolean validMountainArray(int[] A) {
        if (A.length < 3) return false;
        /*記錄首次打破遞增的位置*/
        int left = 0, right = 0;
        /*計(jì)算左山脈*/
        for (int i = 1; i < A.length; i++) {
            if (A[i] <= A[i-1]) {
                break;
            }
            left += 1;
        }
        /*計(jì)算右山脈*/
        for (int i = A.length-2; i >=0 ; i--) {
            if (A[i] <= A[i+1]) {
                break;
            }
            right += 1;
        }
        /*判斷是否是山脈數(shù)組*/
        if (left != 0 && right != 0 && left + right == A.length - 1) {
            return true;
        }
        return false;
    }
}

題目進(jìn)階：845. 數(shù)組中的最長(zhǎng)山脈允蜈，本題在上一題的基礎(chǔ)上做了一些改變，旨在求解數(shù)組中的最長(zhǎng)山脈蒿柳。

我的解法：考慮用動(dòng)態(tài)規(guī)劃求解饶套，
1、定義left[]垒探、right[]數(shù)組分別存儲(chǔ)位置i最長(zhǎng)左山脈和最長(zhǎng)右山脈妓蛮；
2、從左到右計(jì)算left[i]圾叼、從右到左計(jì)算right[i]蛤克；
3捺癞、判斷l(xiāng)eft[i]+right[i]是否等于A.length-1；
時(shí)間復(fù)雜度：O(n)构挤，空間復(fù)雜度：O(n)

class Solution {
    public int longestMountain(int[] A) {
        /*定義數(shù)組存儲(chǔ)dp結(jié)果*/
        int[] left = new int[A.length];
        int[] right = new int[A.length];
        /*首先計(jì)算從左到右的山脈長(zhǎng)度*/
        for (int i = 0; i < A.length; i++) {
            /*left[i] = 0*/
            if (i == 0 || A[i-1] >= A[i]) {
                left[i] = 0;
            } else {
                /*left[i] = left[i-1] + 1*/
                left[i] = left[i-1] + 1;
            }
        }
        /*然后計(jì)算從右到左的山脈長(zhǎng)度*/
        for (int i = A.length-1; i >= 0; i--) {
            /*right[i] = 0*/
            if (i == A.length-1 || A[i+1] >= A[i]) {
                right[i] = 0;
            } else {
                /*right[i] = right[i+1] + 1*/
                right[i] = right[i+1] + 1;
            }
        }
        /*返回左山脈長(zhǎng)度+右山脈長(zhǎng)度的最大值*/
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            /*排除單側(cè)山脈的情況*/
            if (left[i] != 0 && right[i] != 0) {
                max = Math.max(max, left[i] + right[i]);
            }
        }
        /*山脈需滿(mǎn)足長(zhǎng)度大于等于3*/
        return max < 2 ? 0 : max + 1;
    }
}