Description#
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3- There exists some index
i (0-indexed) with 0 < i < arr.length - 1 such that:arr[0] < arr[1] < ... < arr[i - 1] < arr[i]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.
Example 1:
Input: arr = [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: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.
Constraints:
1 <= arr.length <= 1040 <= arr[i] <= 104
Follow up:
- Can you solve it using only one pass?
- Can you solve it in
O(1) space?
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def longestMountain(self, arr: List[int]) -> int:
n = len(arr)
f = [1] * n
g = [1] * n
for i in range(1, n):
if arr[i] > arr[i - 1]:
f[i] = f[i - 1] + 1
ans = 0
for i in range(n - 2, -1, -1):
if arr[i] > arr[i + 1]:
g[i] = g[i + 1] + 1
if f[i] > 1:
ans = max(ans, f[i] + g[i] - 1)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int longestMountain(int[] arr) {
int n = arr.length;
int[] f = new int[n];
int[] g = new int[n];
Arrays.fill(f, 1);
Arrays.fill(g, 1);
for (int i = 1; i < n; ++i) {
if (arr[i] > arr[i - 1]) {
f[i] = f[i - 1] + 1;
}
}
int ans = 0;
for (int i = n - 2; i >= 0; --i) {
if (arr[i] > arr[i + 1]) {
g[i] = g[i + 1] + 1;
if (f[i] > 1) {
ans = Math.max(ans, f[i] + g[i] - 1);
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int longestMountain(vector<int>& arr) {
int n = arr.size();
int f[n];
int g[n];
fill(f, f + n, 1);
fill(g, g + n, 1);
for (int i = 1; i < n; ++i) {
if (arr[i] > arr[i - 1]) {
f[i] = f[i - 1] + 1;
}
}
int ans = 0;
for (int i = n - 2; ~i; --i) {
if (arr[i] > arr[i + 1]) {
g[i] = g[i + 1] + 1;
if (f[i] > 1) {
ans = max(ans, f[i] + g[i] - 1);
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func longestMountain(arr []int) (ans int) {
n := len(arr)
f := make([]int, n)
g := make([]int, n)
for i := range f {
f[i] = 1
g[i] = 1
}
for i := 1; i < n; i++ {
if arr[i] > arr[i-1] {
f[i] = f[i-1] + 1
}
}
for i := n - 2; i >= 0; i-- {
if arr[i] > arr[i+1] {
g[i] = g[i+1] + 1
if f[i] > 1 {
ans = max(ans, f[i]+g[i]-1)
}
}
}
return
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def longestMountain(self, arr: List[int]) -> int:
n = len(arr)
ans = l = 0
while l + 2 < n:
r = l + 1
if arr[l] < arr[r]:
while r + 1 < n and arr[r] < arr[r + 1]:
r += 1
if r < n - 1 and arr[r] > arr[r + 1]:
while r < n - 1 and arr[r] > arr[r + 1]:
r += 1
ans = max(ans, r - l + 1)
else:
r += 1
l = r
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestMountain(int[] arr) {
int n = arr.length;
int ans = 0;
for (int l = 0, r = 0; l + 2 < n; l = r) {
r = l + 1;
if (arr[l] < arr[r]) {
while (r + 1 < n && arr[r] < arr[r + 1]) {
++r;
}
if (r + 1 < n && arr[r] > arr[r + 1]) {
while (r + 1 < n && arr[r] > arr[r + 1]) {
++r;
}
ans = Math.max(ans, r - l + 1);
} else {
++r;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int longestMountain(vector<int>& arr) {
int n = arr.size();
int ans = 0;
for (int l = 0, r = 0; l + 2 < n; l = r) {
r = l + 1;
if (arr[l] < arr[r]) {
while (r + 1 < n && arr[r] < arr[r + 1]) {
++r;
}
if (r + 1 < n && arr[r] > arr[r + 1]) {
while (r + 1 < n && arr[r] > arr[r + 1]) {
++r;
}
ans = max(ans, r - l + 1);
} else {
++r;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func longestMountain(arr []int) (ans int) {
n := len(arr)
for l, r := 0, 0; l+2 < n; l = r {
r = l + 1
if arr[l] < arr[r] {
for r+1 < n && arr[r] < arr[r+1] {
r++
}
if r+1 < n && arr[r] > arr[r+1] {
for r+1 < n && arr[r] > arr[r+1] {
r++
}
ans = max(ans, r-l+1)
} else {
r++
}
}
}
return
}
|
