The Valid Mountain Array Algorithm

  • 时间:2020-09-30 16:23:25
  • 分类:网络文摘
  • 阅读:72 次

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[len(B) - 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

One Pass Algorithm to Judge Valid Mountain Array

Given a mountain array, the peak point must be somewhere in the middle, the left and right should be all in descending order. We can iterate (one pass) the array from the left, to find the peak (as we are climbing up the hill) which is the last increasing element, then we continue iterating the array as we are walking down the hill.

The array is a mountain array if and only if the steps left and right are non-zero, and we have also reached the end of the array when climbing down.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean validMountainArray(int[] A) {        
        int peak = 0, left = 0, right = 0;
        // optional: if (A.length < 3) return false;
        while ((peak < A.length - 1) && (A[peak] < A[peak + 1])) { 
            peak ++; 
            left ++; 
        };
        // optional: if ((peak == 0) || (peak == A.length - 1)) return false;
        while ((peak < A.length - 1) && (A[peak] > A[peak + 1])) { 
            peak ++; 
            right ++; 
        };        
        return (left * right > 0) && (peak == A.length - 1);
    }
}
class Solution {
    public boolean validMountainArray(int[] A) {        
        int peak = 0, left = 0, right = 0;
        // optional: if (A.length < 3) return false;
        while ((peak < A.length - 1) && (A[peak] < A[peak + 1])) { 
            peak ++; 
            left ++; 
        };
        // optional: if ((peak == 0) || (peak == A.length - 1)) return false;
        while ((peak < A.length - 1) && (A[peak] > A[peak + 1])) { 
            peak ++; 
            right ++; 
        };        
        return (left * right > 0) && (peak == A.length - 1);
    }
}

The above Java solution is O(N) in time and O(1) constant in space. You could write similar implementations easily using other programming languages such as C/C++, or Javascript.

The following implementation is in C++ where we have to pay attention to the vector.size() method which returns size_t (which is unsigned). Thus we have to convert it implicitly/explicitly to signed integer otherwise size() – 1 will cause integer underflow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool validMountainArray(vector<int>& A) {
        int peak = 0, left = 0, right = 0;
        int size = A.size();
        // optional: if (A.length < 3) return false;
        while ((peak < size - 1) && (A[peak] < A[peak + 1])) { 
            peak ++; 
            left ++; 
        };
        // optional: if ((peak == 0) || (peak == A.length - 1)) return false;
        while ((peak < size - 1) && (A[peak] > A[peak + 1])) { 
            peak ++; 
            right ++; 
        };        
        return (left * right > 0) && (peak == size - 1);        
    }
};
class Solution {
public:
    bool validMountainArray(vector<int>& A) {
        int peak = 0, left = 0, right = 0;
        int size = A.size();
        // optional: if (A.length < 3) return false;
        while ((peak < size - 1) && (A[peak] < A[peak + 1])) { 
            peak ++; 
            left ++; 
        };
        // optional: if ((peak == 0) || (peak == A.length - 1)) return false;
        while ((peak < size - 1) && (A[peak] > A[peak + 1])) { 
            peak ++; 
            right ++; 
        };        
        return (left * right > 0) && (peak == size - 1);        
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
学习古人的智慧  关于清明节的小作文200字  地震中的父与子500字  二年级作文家乡的水  都是马虎惹得祸作文200字  美味在眼前,我手煮我心  离殇  数学题:若用a型箱,正好要装800箱  数学题:神舟五号飞行轨道的近地点高度为200km  数学题:汽车在途中停了一小时,客车速度比汽车慢 
评论列表
添加评论