# 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 - 1` such that `B[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:

1. `0 <= A.length <= 10000`
2. `0 <= A[i] <= 10000`

• Can you solve it using only one pass?
• Can you solve it in `O(1)` space?

``````class Solution {
public:
int longestMountain(vector<int>& A) {
int res = 0, n = A.size();
vector<int> up(n), down(n);
for (int i = n - 2; i >= 0; --i) {
if (A[i] > A[i + 1]) down[i] = down[i + 1] + 1;
}
for (int i = 1; i < n; ++i) {
if (A[i] > A[i - 1]) up[i] = up[i - 1] + 1;
if (up[i] > 0 && down[i] > 0) res = max(res, up[i] + down[i] + 1);
}
return res;
}
};
``````

``````class Solution {
public:
int longestMountain(vector<int>& A) {
int res = 0, up = 0, down = 0, n = A.size();
for (int i = 1; i < n; ++i) {
if ((down && 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) res = max(res, up + down + 1);
}
return res;
}
};
``````

``````class Solution {
public:
int longestMountain(vector<int>& A) {
int res = 0, i = 0, n = A.size();
while (i < n - 1) {
while (i < n - 1 && A[i] >= A[i + 1]) ++i;
int peak = i;
while (peak < n - 1 && A[peak] < A[peak + 1]) ++peak;
int j = peak;
while (j < n - 1 && A[j] > A[j + 1]) ++j;
if (i < peak && peak < j) res = max(res, j - i + 1);
i = j;
}
return res;
}
};
``````

``````class Solution {
public:
int longestMountain(vector<int>& A) {
int res = 0, n = A.size();
for (int i = 1; i < n - 1; ++i) {
if (A[i - 1] < A[i] && A[i + 1] < A[i]) {
int left = i - 1, right = i + 1;
while (left > 0 && A[left - 1] < A[left]) --left;
while (right < n - 1 && A[right] > A[right + 1]) ++right;
res = max(res, right - left + 1);
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/845

https://leetcode.com/problems/longest-mountain-in-array/

https://leetcode.com/problems/longest-mountain-in-array/discuss/176952/Java-1-pass-and-O(1)-space-beats-100

https://leetcode.com/problems/longest-mountain-in-array/discuss/135593/C%2B%2BJavaPython-1-pass-and-O(1)-space

https://leetcode.com/problems/longest-mountain-in-array/discuss/150136/Simple-O(n)-one-pass-O(1)-space-Java-AC-solution-beats-99.05

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation