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; }
近期评论