Problem
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
Solution
Use has_up and has_down to track whether we have A[i] > A[i – 1] and A[i] < A[i – 1] receptively.
return false if any of the following happened:
- size(A) < 3
- has_down happened before has_up
- not has_down or not has_up
- A[i – 1] < A[i] after has_down
- A[i – 1] > A[i] before has_up
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua, 24 ms class Solution { public: bool validMountainArray(vector<int>& A) { if (A.size() < 3) return false; bool has_up = false; bool has_down = false; for (int i = 1; i < A.size(); ++i) { if (A[i] > A[i - 1]) { if (has_down) return false; has_up = true; } else if (A[i] < A[i - 1]){ if (!has_up) return false; has_down = true; } else { return false; } } return has_up && has_down; } }; |