LeetCode 845中等双指针/数组扫描
数组中的最长山脉 图解题解
这道题到底在问什么
给定数组 arr，返回最长山脉子数组的长度；不存在山脉返回 0。山脉需先严格升再严格降，左右两侧长度都至少为 1。
- 输入
- arr=[2,1,4,7,3,2,5]
- 输出
- 5 （山脉 [1,4,7,3,2]）
- 输入
- arr=[2,2,2]
- 输出
- 0 （没有严格升降）
最优解：一步一步想明白
- 3记住「先找峰顶（两边都比它矮），再向左右扩展量长度」，下面每帧都在套它。
- 4看 i=1（值 1）是不是峰顶：左边 2 < 1 就不成立，不是峰顶，i 前进一格。
- 5看 i=2（值 4）是不是峰顶：左边 1 < 4 成立，但右边 4 > 7 不成立，不是峰顶，i 前进一格。
- 6i=3（值 7）左边 4 更小、右边 6 也更小，是个峰顶（绿色）！接下来向左右扩展看这座山有多长。
- 7向左走：4 < 7，左边还在严格上升，左边界 l 移到 2，绿色山脉向左长一格。
- 8向左走：1 < 4，左边还在严格上升，左边界 l 移到 1，绿色山脉向左长一格。
- 9向右走：7 > 6，右边还在严格下降，右边界 r 移到 4，绿色山脉向右长一格。
- 10向右走：6 > 3，右边还在严格下降，右边界 r 移到 5，绿色山脉向右长一格。
- 11这座山脉从下标 1 到 5，长度 5。比之前的最长还长，刷新答案为 5。
- 12关键一步：这座山下降坡上的点不可能再是别的峰顶，所以把 i 直接跳到右端 5，下一轮从 6 开始——这正是代码里的 i=r，也是整体保持线性 O(n) 的原因。
- 13看 i=6（值 5）是不是峰顶：左边 3 < 5 成立，但右边 5 > 8 不成立，不是峰顶，i 前进一格。
- 14看 i=7（值 8）是不是峰顶：左边 5 < 8 成立，但右边 8 > 9 不成立，不是峰顶，i 前进一格。
- 15i=8（值 9）左边 8 更小、右边 2 也更小，是个峰顶（绿色）！接下来向左右扩展看这座山有多长。
- 16向左走：8 < 9，左边还在严格上升，左边界 l 移到 7，绿色山脉向左长一格。
- 17向左走：5 < 8，左边还在严格上升，左边界 l 移到 6，绿色山脉向左长一格。
- 18向左走：3 < 5，左边还在严格上升，左边界 l 移到 5，绿色山脉向左长一格。
- 19向右走：9 > 2，右边还在严格下降，右边界 r 移到 9，绿色山脉向右长一格。
- 20向右走：2 > 1，右边还在严格下降，右边界 r 移到 10，绿色山脉向右长一格。
- 21这座山脉从下标 5 到 10，长度 6。比之前的最长还长，刷新答案为 6。
- 22关键一步：这座山下降坡上的点不可能再是别的峰顶，所以把 i 直接跳到右端 10，下一轮从 11 开始——这正是代码里的 i=r，也是整体保持线性 O(n) 的原因。
- 23扫完所有峰顶，最长的一座山脉是绿色这 6 个（3→5→8→9→2→1）：从 3 一路严格升到峰顶，再严格降到 1。答案 6。
⚠️ 容易写错的地方
✗ 错：把「严格」当成「非严格」
✓ 对：相等既不算升也不算降
[2,2,2] 没有山脉，答案是 0 不是 3
✗ 错：只有上坡或只有下坡也算山脉
✓ 对：必须先升再降，两侧长度都≥1
单调序列不是山脉，长度按 0 算
✗ 错：扩展后忘了把 i 跳到 r
✓ 对：i = r 再继续，避免重复扫已属于山脉的坡
不跳虽不影响正确性，但会退化效率
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def longestMountain(self, arr: List[int]) -> int:
n = len(arr)
ans = 0
i = 1
while i < n - 1:
if arr[i - 1] < arr[i] > arr[i + 1]:
l = r = i
while l > 0 and arr[l - 1] < arr[l]:
l -= 1
while r + 1 < n and arr[r] > arr[r + 1]:
r += 1
ans = max(ans, r - l + 1)
i = r
i += 1
return ansC++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int longestMountain(vector<int>& arr) {
int n = arr.size(), ans = 0, i = 1;
while (i < n - 1) {
if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
int l = i, r = i;
while (l > 0 && arr[l - 1] < arr[l]) --l;
while (r + 1 < n && arr[r] > arr[r + 1]) ++r;
ans = max(ans, r - l + 1);
i = r;
}
++i;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int longestMountain(int[] arr) {
int n = arr.length, ans = 0, i = 1;
while (i < n - 1) {
if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
int l = i, r = i;
while (l > 0 && arr[l - 1] < arr[l]) l--;
while (r + 1 < n && arr[r] > arr[r + 1]) r++;
ans = Math.max(ans, r - l + 1);
i = r;
}
i++;
}
return ans;
}
}复杂度
时间
O(n)
下降坡不反复当峰顶,各点常数次触碰
空间
O(1)
只用几个下标变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组中的最长山脉 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
除了「枚举峰顶 + 扩展」，还有别的线性解吗？+
有。可以一次遍历维护 up（当前已上升的步数）和 down（当前已下降的步数）：遇到上升且之前在下降就重置 up=1、down=0；当 up>0 且 down>0 时用 up+down+1 更新答案。两种都是 O(n) O(1)，本质相同。
为什么山脉最短是 3？+
定义要求左右两侧长度都至少为 1，再加峰顶本身，所以最少是「1 个上升 + 峰顶 + 1 个下降」= 3 个元素。长度小于 3 一律不算山脉，返回 0。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组中的最长山脉 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。