Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:
B.length >= 3
There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
(Note that B could be any subarray of A, including the entire array A.)
Given an array A of integers, return the length of the longest mountain.
Return 0 if there is no mountain.
Example 1:
Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.
Example 2:
Input: [2,2,2]
Output: 0
Explanation: There is no mountain.
Note:
0 <= A.length <= 10000
0 <= A[i] <= 10000
Follow up:
Can you solve it using only one pass?
Can you solve it in O(1) space?
Solution1:
class Solution {
public int longestMountain(int[] A) {
if (A.length <= 2) return 0;
boolean up = A[1] > A[0] ? true : false;
boolean hasAnswer = false;
int prev = A[1];
int curLen = up ? 2 : 1;
int i = 2, max = 0;
while (i < A.length) {
int val = A[i];
if (up) {
if (val > prev) {
curLen ++;
} else if (val < prev) {
hasAnswer = true;
if (curLen > 1) {
curLen ++;
}
up = false;
} else {
curLen = 1;
}
} else {
if (val < prev) {
curLen ++;
} else if (val >= prev) {
up = true;
max = Math.max(max, curLen);
curLen = val == prev ? 1 : 2;
}
}
// System.out.println(i + ", " + curLen);
prev = val;
i ++;
}
if (hasAnswer) {
max = Math.max(max, curLen);
}
return max >= 3 ? max : 0;
}
}
Solution2:
class Solution {
public int longestMountain(int[] A) {
int maxMnt = 0;
int n = A.length;
int i = 1;
while (i < n) {
while(i < n && A[i-1] == A[i])
++i;
int up = 0;
while(i < n && A[i-1] < A[i]) {
++up;
++i;
}
int down = 0;
while(i < n && A[i-1] > A[i]) {
++down;
++i;
}
if (up > 0 && down > 0)
maxMnt = Math.max(maxMnt, up+down+1);
}
return maxMnt;
}
}