You may recall that an array arr is a mountain array if and only if:
arr.length >= 3i (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] <= 104Follow up:
O(1) space?Using extra space and 3 passes
Using 2 arrays to record the longest increasing and decrasing from current number. Then join both values to find the longest mountain.
1 class Solution: 2 def longestMountain(self, arr: List[int]) -> int: 3 if not arr or len(arr) < 3: 4 return 0 5 array_len = len(arr) 6 increasing, decreasing = [0] * array_len, [0] * array_len 7 for i in range (1, array_len): 8 if arr[i] > arr[i - 1]: 9 increasing[i] = increasing[i - 1] + 1 10 for i in range (array_len - 2, -1, -1): 11 if arr[i] > arr[i + 1]: 12 decreasing[i] = decreasing[i + 1] + 1 13 14 max_length = 0 15 for i in range(1, len(arr) - 1): 16 if increasing[i] and decreasing[i]: 17 max_length = max(max_length, increasing[i] + decreasing[i] + 1) 18 return max_length if max_length >= 3 else 0
Approach 2: using one pass and no extra arrays. The idea is if there is a mountain, we must have up hill and down hill at the same time.
1 class Solution: 2 def longestMountain(self, arr: List[int]) -> int: 3 if not arr or len(arr) < 3: 4 return 0 5 i = 1 6 max_len = 0 7 arr_len = len(arr) 8 while i < arr_len: 9 while i < arr_len and arr[i] == arr[i - 1]: 10 i += 1 11 increasing_count = decreasing_count = 0 12 while i < arr_len and arr[i - 1] < arr[i]: 13 increasing_count += 1 14 i += 1 15 16 while i < arr_len and arr[i - 1] > arr[i]: 17 decreasing_count += 1 18 i += 1 19 20 if increasing_count and decreasing_count: 21 max_len = max(max_len, increasing_count + decreasing_count + 1) 22 23 return max_len
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。