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
Solution:
The idea is to:
1. check the array is increasing and find the peak
2. check the rest of array is decreasing
Since we check each element at most twice. The time complexity is O(n).
Code:
class Solution { public boolean validMountainArray(int[] A) { if (A == null || A.length < 3) { return false; } int peak = 0; while (peak + 1 < A.length) { if (A[peak + 1] <= A[peak]) { break; } peak++; } if (peak == 0 || peak == A.length - 1) { return false; } while (peak + 1 < A.length) { if (A[peak] <= A[peak + 1]) { return false; } peak++; } return true; } }