Welcome to Subscribe On Youtube
845. Longest Mountain in Array
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) with0 < i < arr.length - 1such 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: Dynamic Programming
We define two arrays $f$ and $g$, where $f[i]$ represents the length of the longest rising subsequence ending with $arr[i]$, and $g[i]$ represents the length of the longest descending subsequence starting with $arr[i]$. Then for each subscript $i$, if $f[i] \gt 1$ and $g[i] \gt 1$, then the length of the mountain with $arr[i]$ as the top is $f[i] + g[i] - 1$, we only need to enumerate all $i$ and find the largest value.
Time complexity $O(n)$, space complexity $O(n)$. Where $n$ is the length of the array $arr$.
Solution 2: Translated Upstream Explanation
We can enumerate the left foot of the mountain and then look to the right for the right foot of the mountain. We can use two pointers $l$ and $r$, where $l$ represents the subscript of the foot of the mountain on the left, and $r$ represents the subscript of the foot of the right mountain. Initially, $l=0$, $r=0$, and then we move $r$ to the right to find the location of the top of the mountain. At this time, judge Does $r$ satisfy $r + 1 \lt n$ and $arr[r] \gt arr[r + 1]$, if so, we continue to move $r$ to the right until we find the location of the foot of the mountain on the right, at this time the length of the mountain is $r - l + 1$, we update the answer, and then update the value of $l$ to $r$, keep looking for the next mountain range.
Time complexity $O(n)$, where $n$ is the length of the array $arr$. Space complexity $O(1)$.
-
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; } } // Solution 2 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; } } -
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; } }; // Solution 2 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; } }; -
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 # Solution 2 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 -
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 } // Solution 2 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 } -
function longestMountain(arr: number[]): number { const n = arr.length; const f: number[] = Array(n).fill(1); const g: number[] = Array(n).fill(1); for (let i = 1; i < n; ++i) { if (arr[i] > arr[i - 1]) { f[i] = f[i - 1] + 1; } } let ans = 0; for (let 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; } // Solution 2 function longestMountain(arr: number[]): number { const n = arr.length; let ans = 0; for (let 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; }