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?
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution:
def longestMountain(self, arr: List[int]) -> int:
n = len(arr)
up, down = [0] * n, [0] * n
for i in range(1, n):
if arr[i] > arr[i - 1]:
up[i] = up[i - 1] + 1
for i in range(n-2, -1, -1):
if arr[i] > arr[i + 1]:
down[i] = down[i + 1] + 1
return max(
[u + d + 1 for u, d in zip(up, down) if u and d]
or [0]
)
'''
One pass
'''
class Solution:
def longestMountain(self, arr: List[int]) -> int:
n = len(arr)
res = up = down = 0
for i in range(1, n):
if (
down and arr[i - 1] < arr[i]
or arr[i - 1] == arr[i]
):
up = down = 0
up += arr[i - 1] < arr[i]
down += arr[i - 1] > arr[i]
if up and down:
res = max(res, up + down + 1)
return res
|