https://leetcode.com/problems/longest-mountain-in-array/
https://leetcode.com/problems/longest-mountain-in-array/discuss/135593/C%2B%2BJavaPython-1-pass-and-O(1)-space
X. Two Pointers
![Worked example of A = [1,2,3,2,1,0,2,3,1]](https://leetcode.com/problems/Figures/845/diagram1.png)
直接遍历一遍，找到一个上升点然后开始遍历，处理一些小情况即可
X. Left + right array (DP)
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-845-longest-mountain-in-array/
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 - 1such thatB[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 <= 100000 <= A[i] <= 10000
https://leetcode.com/problems/longest-mountain-in-array/discuss/135593/C%2B%2BJavaPython-1-pass-and-O(1)-space
We have already many 2-pass or 3-pass problems, like 821. Shortest Distance to a Character.
They have almost the same idea.
One forward pass and one backward pass.
Maybe another pass to get the final result, or you can merge it in one previous pass.
They have almost the same idea.
One forward pass and one backward pass.
Maybe another pass to get the final result, or you can merge it in one previous pass.
Explanation:
In this problem, we take one forward pass to count up hill length (to every point).
We take another backward pass to count down hill length (from every point).
Finally a pass to find max(up[i] + down[i] + 1) where up[i] and down[i] should be positives.
In this problem, we take one forward pass to count up hill length (to every point).
We take another backward pass to count down hill length (from every point).
Finally a pass to find max(up[i] + down[i] + 1) where up[i] and down[i] should be positives.
public int longestMountain(int[] A) {
int N = A.length, res = 0;
int[] up = new int[N], down = new int[N];
for (int i = N - 2; i >= 0; --i) if (A[i] > A[i + 1]) down[i] = down[i + 1] + 1;
for (int i = 0; i < N; ++i) {
if (i > 0 && A[i] > A[i - 1]) up[i] = up[i - 1] + 1;
if (up[i] > 0 && down[i] > 0) res = Math.max(res, up[i] + down[i] + 1);
}
return res;
Can you solve this problem with only one pass?Can you solve this problem in O(1) space?
In this solution, I count up length and down length.
Both up and down length are clear to 0 when A[i - 1] == A[i] or down > 0 && A[i - 1] < A[i].
public int longestMountain(int[] A) {
int res = 0, up = 0, down = 0;
for (int i = 1; i < A.length; ++i) {
if (down > 0 && A[i - 1] < A[i] || A[i - 1] == A[i]) up = down = 0;
if (A[i - 1] < A[i]) up++;
if (A[i - 1] > A[i]) down++;
if (up > 0 && down > 0 && up + down + 1 > res) res = up + down + 1;
}
return res;
}
X. Two Pointers
Without loss of generality, a mountain can only start after the previous one ends.
This is because if it starts before the peak, it will be smaller than a mountain starting previous; and it is impossible to start after the peak.
Algorithm
For a starting index
base, let's calculate the length of the longest mountain A[base], A[base+1], ..., A[end].
If such a mountain existed, the next possible mountain will start at
base = end; if it didn't, then either we reached the end, or we have A[base] > A[base+1] and we can start at base + 1.
Example
Here is a worked example on the array
A = [1, 2, 3, 2, 1, 0, 2, 3, 1]:base starts at 0, and end travels using the first while loop to end = 2 (A[end] = 3), the potential peak of this mountain. After, it travels to end = 5 (A[end] = 0) during the second while loop, and a candidate answer of 6 (base = 0, end = 5) is recorded.
Afterwards, base is set to
5 and the process starts over again, with end = 7 the peak of the mountain, and end = 8 the right boundary, and the candidate answer of 4 (base = 5, end = 8) being recorded.
public int longestMountain(int[] A) {
int N = A.length;
int ans = 0, base = 0;
while (base < N) {
int end = base;
// if base is a left-boundary
if (end + 1 < N && A[end] < A[end + 1]) {
// set end to the peak of this potential mountain
while (end + 1 < N && A[end] < A[end + 1])
end++;
// if end is really a peak..
if (end + 1 < N && A[end] > A[end + 1]) {
// set end to the right-boundary of mountain
while (end + 1 < N && A[end] > A[end + 1])
end++;
// record candidate answer
ans = Math.max(ans, end - base + 1);
}
}
base = Math.max(end, base + 1);
}
return ans;
}
X. https://buptwc.com/2018/06/04/Leetcode-845-Longest-Mountain-in-Array/直接遍历一遍，找到一个上升点然后开始遍历，处理一些小情况即可
class Solution(object): def longestMountain(self, A): """ :type A: List[int] :rtype: int """ # O(n) time, O(1) space i,n = 0,len(A) res = 0 while i < n-1: #找到一个上升点 if A[i] < A[i+1]: # 先找上升序列 j = i+1 while j < n and A[j] > A[j-1]: j += 1 # 如若遍历到数组末尾直接返回结果 if j == n: return res # 这个判断语句处理[1,2,2,0]这种情况 if A[j] != A[j-1]: while j < n and A[j] < A[j-1]: j += 1 res = max(res,j-i) i = j-2 else: i = j-1 i += 1 return reshttps://leetcode.com/problems/longest-mountain-in-array/discuss/165667/1-pass-Java-Two-Point-Solution
X. Left + right array (DP)
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-845-longest-mountain-in-array/
int longestMountain(vector<int>& A) {
vector<int> inc(A.size());
vector<int> dec(A.size());
for (int i = 1; i < A.size(); ++i)
if (A[i] > A[i - 1]) inc[i] = inc[i - 1] + 1;
for (int i = A.size() - 2; i > 0; --i)
if (A[i] > A[i + 1]) dec[i] = dec[i + 1] + 1;
int ans = 0;
for (int i = 0; i < A.size(); ++i)
if (inc[i] && dec[i])
ans = max(ans, inc[i] + dec[i] + 1);
return ans >= 3 ? ans : 0;
}
