LeetCode 题解工作台
数组中的最长山脉
把符合下列属性的数组 arr 称为 山脉数组 ： arr.length >= 3 存在下标 i （ 0 ），满足 arr[0] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 给出一个整数数组 arr ，返回最长山脉子数组的长度。如果不存在山脉子数组，…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义两个数组 和 ，其中 表示以 结尾的最长上升子序列的长度，而 表示以 开头的最长下降子序列的长度。那么对于每个下标 ，如果 $f[i] \gt 1$ 且 $g[i] \gt 1$，那么以 为山顶的山脉的长度为 $f[i] + g[i] - 1$，我们只需要枚举所有的 ，找出最大的那个值即可。 时间复杂度 ，空间复杂度 。其中 为数组 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
把符合下列属性的数组 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)空间解决此问题吗？
解题思路
方法一：预处理 + 枚举
我们定义两个数组 和 ，其中 表示以 结尾的最长上升子序列的长度，而 表示以 开头的最长下降子序列的长度。那么对于每个下标 ，如果 且 ，那么以 为山顶的山脉的长度为 ，我们只需要枚举所有的 ，找出最大的那个值即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def longestMountain(self, arr: List[int]) -> int:
n = len(arr)
f = [1] * n
g = [1] * n
for i in range(1, n):
if arr[i] > arr[i - 1]:
f[i] = f[i - 1] + 1
ans = 0
for i in range(n - 2, -1, -1):
if arr[i] > arr[i + 1]:
g[i] = g[i + 1] + 1
if f[i] > 1:
ans = max(ans, f[i] + g[i] - 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
They may ask about handling plateaus or equal consecutive elements.
- question_mark
Expect questions on why two pointers suffice instead of nested loops.
- question_mark
Be ready to explain the state transition from increasing to decreasing sequences.
常见陷阱
外企场景- error
Counting plateaus as part of a mountain peak incorrectly.
- error
Failing to require at least three elements for a valid mountain.
- error
Overcomplicating the solution with nested loops instead of linear expansion from peaks.
进阶变体
外企场景- arrow_right_alt
Find the total number of mountains in the array rather than the longest.
- arrow_right_alt
Compute the longest mountain if the array can contain negative numbers.
- arrow_right_alt
Return the indices of the longest mountain subarray instead of its length.