问题描述
LeetCode 845. 数组中的最长山脉 (opens in a new tab)，难度中等。
把符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3- 存在下标
i（0 < i < arr.length - 1），满足arr[0] < arr[1] < ... < arr[i - 1] < arr[i]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。
示例 1
输入：arr = [2,1,4,7,3,2,5] 输出：5 解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。
示例 2
输入：arr = [2,2,2] 输出：0 解释：不存在山脉子数组。
提示：
1 <= arr.length <= 1040 <= arr[i] <= 104
进阶：
- 你可以仅用一趟扫描解决此问题吗？
- 你可以用
O(1)空间解决此问题吗？
题解
双向扫描
解题思路：我们首先需要找到所有的递增子数组和递减子数组，如果一个位置同时满足递增和递减的条件，那么我们就找到了一个山脉。最后通过计算该山脉的长度，并更新最大值。
Solution.java
class Solution {
public int longestMountain(int[] arr) {
if (arr.length < 3) return 0;
int[] up = new int[arr.length];
int[] down = new int[arr.length];
// 寻找左脉递增序列
for (int i = 1; i < arr.length; ++i) {
if (arr[i] > arr[i - 1]) {
up[i] = up[i - 1] + 1;
}
}
// 寻找右脉递减序列
for (int i = arr.length - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
down[i] = down[i + 1] + 1;
}
}
int result = 0;
for (int i = 1; i < arr.length - 1; ++i) {
// 判断 i 是否是山顶
if (up[i] > 0 && down[i] > 0) {
// 左山脉 + 右山脉 + 山顶
result = Math.max(result, up[i] + down[i] + 1);
}
}
return result;
}
}