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
iwith0 < i < A.length - 1such 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 <= 100000 <= A[i] <= 10000
Idea 1. 遍历验证是否up-down once
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public boolean validMountainArray(int[] A) {
int n = A.length;
// if(n < 3) {
// return false;
// }
int left = 0;
while(left+1 < n && A[left] < A[left+1]) {
++left;
}
if(left == 0 || left == n-1) {
return false;
}
while(left+1 < n && A[left] > A[left+1]) {
++left;
}
if(left == n-1) {
return true;
}
return false;
}
}
Idea 1. 网上看到的有意思的解法，both two men walking up from the bottom
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public boolean validMountainArray(int[] A) {
int n = A.length;
int left = 0;
while(left+1 < n && A[left] < A[left+1]) {
++left;
}
int right = n-1;
while(right - 1 >= 0 && A[right-1] > A[right]) {
--right;
}
return left == right && left!= 0 && right != n-1;
}
}