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:

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
  • 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:

    1. 0 <= A.length <= 10000
    2. 0 <= A[i] <= 10000 

Idea 1.  遍历验证是否up-down once

Time complexity: O(n)

Space complexity: O(1)

 1 class Solution {
 2     public boolean validMountainArray(int[] A) {
 3         int n = A.length;
 4         // if(n < 3) {
 5         //     return false;
 6         // }
 7         
 8         int left = 0;
 9         while(left+1 < n && A[left] < A[left+1]) {
10             ++left;
11         }
12         if(left == 0 || left == n-1) {
13             return false;
14         }
15         
16         while(left+1 < n && A[left] > A[left+1]) {
17             ++left;
18         }
19         
20         if(left == n-1) {
21             return true;
22         }
23         
24         return false;
25     }
26 }

Idea 1. 网上看到的有意思的解法，both two men walking up from the bottom

Time complexity: O(n)

Space complexity: O(1)

 1 class Solution {
 2     public boolean validMountainArray(int[] A) {
 3         int n = A.length;
 4         
 5         int left = 0;
 6         while(left+1 < n && A[left] < A[left+1]) {
 7             ++left;
 8         }
 9         
10         int right = n-1;
11         while(right - 1 >= 0 && A[right-1] > A[right]) {
12             --right;
13         }
14         
15         return left == right && left!= 0 && right != n-1;
16     }
17 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄