941. Valid Mountain Array.md

title	toc	date	tags	top
941. Valid Mountain Array	false	2017-10-30	Leetcode Array	941

Given an array A of integers, return true if and only if it is a valid mountain array.

Recall that A is a mountain array if and only if:

• A.length >= 3
• There exists some $i$ with 0 < $i$ < A.length - 1 such that:
  • A[0] < A[1] < ... A[$i$-1] < A[$i$]
  • A[$i$] > A[$i$+1] > ... > A[B.length - 1]

Example 1:

Input: [2,1]
Output: false
Example 2:

Input: [3,5,5]
Output: false
Example 3:

Input: [0,3,2,1]
Output: true

Note:

• 0 <= A.length <= 10000
• 0 <= A[$i$] <= 10000

分析

考查基本的数组操作。

一个人从一侧开始爬山。

public boolean validMountainArray(int[] A) {
    if (A == null || A.length < 3) return false;
    int n = A.length;
    int i;
    for (i = 1; i < n && A[i] > A[i - 1]; i++) ;
    if (i == 1 || i == n) return false;
    for (; i < n && A[i] < A[i - 1]; i++) ;
    if (i != n) return false;
    
    return true;
}

两个人分别从山的两侧开始爬，如果是山，他们会在山顶相遇。

public boolean validMountainArray(int[] A) {
    int n = A.length, i = 0, j = n - 1;
    while (i + 1 < n && A[i] < A[i + 1]) i++;
    while (j > 0 && A[j - 1] > A[j]) j--;
    return i > 0 && i == j && j < n - 1;
}