LeetCode 题解工作台
有效的山脉数组
给定一个整数数组 arr ，如果它是有效的山脉数组就返回 true ，否则返回 false 。 让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组： arr.length >= 3 在 0 条件下，存在 i 使得： arr[0] arr[i] > arr[i+1] > ... > ar…
1
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·driven
答案摘要
我们首先判断数组的长度是否小于 ，如果小于 ，那么一定不是山脉数组，直接返回 `false`。 然后，我们使用指针 从数组的左端开始向右移动，直到找到一个位置 ，使得 $arr[i] > arr[i + 1]$。然后，我们使用指针 从数组的右端开始向左移动，直到找到一个位置 ，使得 $arr[j] > arr[j - 1]$。如果满足条件 $i = j$，那么就说明数组 是一个山脉数组。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：
arr.length >= 3- 在
0 < i < arr.length - 1条件下，存在i使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
示例 1：
输入：arr = [2,1] 输出：false
示例 2：
输入：arr = [3,5,5] 输出：false
示例 3：
输入：arr = [0,3,2,1] 输出：true
提示：
1 <= arr.length <= 1040 <= arr[i] <= 104
解题思路
方法一：双指针
我们首先判断数组的长度是否小于 ，如果小于 ，那么一定不是山脉数组，直接返回 false。
然后，我们使用指针 从数组的左端开始向右移动，直到找到一个位置 ，使得 。然后，我们使用指针 从数组的右端开始向左移动，直到找到一个位置 ，使得 。如果满足条件 ，那么就说明数组 是一个山脉数组。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def validMountainArray(self, arr: List[int]) -> bool:
n = len(arr)
if n < 3:
return False
i, j = 0, n - 1
while i + 1 < n - 1 and arr[i] < arr[i + 1]:
i += 1
while j - 1 > 0 and arr[j - 1] > arr[j]:
j -= 1
return i == j
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates an understanding of monotonic sequences.
- question_mark
The candidate correctly identifies and handles edge cases like short arrays.
- question_mark
The candidate approaches the problem efficiently, with an O(n) solution.
常见陷阱
外企场景- error
Forgetting that the peak must be neither the first nor last element of the array.
- error
Mistaking non-strictly increasing or decreasing sequences as valid.
- error
Not handling cases where the array is too short or contains duplicate elements properly.
进阶变体
外企场景- arrow_right_alt
Handle arrays with duplicate values, where the peak may not be strictly increasing or decreasing.
- arrow_right_alt
Extend the problem to handle arrays with more complex conditions, like multiple peaks.
- arrow_right_alt
Optimize for large arrays by considering early exits when the array fails any of the conditions.