LeetCode 941. 有效的山脉数组
题目描述
题意分析
判断整个数组是否先严格上升、再严格下降。峰顶必须在内部，上坡和下坡都至少有一段相邻变化，因此数组至少包含三个元素；相邻相等形成的平台不合法。
解法：上坡与下坡两阶段扫描
核心思路
[!blue]
用一个指针
i从头开始，只要arr[i] < arr[i+1]就继续前进。停下时，[0,i]已经是一段完整的严格上升前缀，i是唯一需要考虑的峰顶位置：选得更早会把后续上升放进下坡，选得更晚又必须跨过当前这次非上升变化，无法保持上坡。若
i==0，说明从一开始就没有上坡；若i==n-1，说明整个数组都在上升、没有下坡。这两种情况都应立即返回false，从而保证峰顶位于内部。随后从这个位置继续前进，但条件改为
arr[i] > arr[i+1]。只有走到数组末尾，才说明峰顶之后全部严格下降；若停在中途，就存在平台或再次上升，整个数组不是山脉。成功时，第一阶段保证至少一次上升，内部峰顶加上第二阶段到达末尾保证至少一次下降，两阶段又覆盖了全部相邻关系，恰好满足定义。反过来，任何合法山脉都会在真实峰顶结束第一阶段，并沿下降段走到末尾，所以不会漏判。
解题步骤
- 长度小于三直接返回 false。
- 沿严格上升推进指针。
- 排除峰顶在首尾的情况。
- 沿严格下降继续，判断是否到达末尾。
平台会同时阻止严格上升与严格下降；纯递增或纯递减会被峰顶位置检查排除。判断的是整个数组，找到局部峰顶并不足以返回成功。
代码实现
class Solution {
public boolean validMountainArray(int[] arr) {
int n = arr.length;
if (n < 3) {
return false;
}
int i = 0;
// 严格上升才前进，遇到相等或下降就停在峰顶候选位。
while (i + 1 < n && arr[i] < arr[i + 1]) {
i++;
}
// 峰顶不能落在两端，否则缺上坡或缺下坡。
if (i == 0 || i == n - 1) {
return false;
}
// 从峰顶继续严格下降。
while (i + 1 < n && arr[i] > arr[i + 1]) {
i++;
}
// 只有恰好走到末尾，才说明中间没有平台或二次上升。
return i == n - 1;
}
}
func validMountainArray(arr []int) bool {
n := len(arr)
if n < 3 {
return false
}
i := 0
// 严格上升才前进，遇到相等或下降就停在峰顶候选位。
for i+1 < n && arr[i] < arr[i+1] {
i++
}
// 峰顶不能落在两端，否则缺上坡或缺下坡。
if i == 0 || i == n-1 {
return false
}
// 从峰顶继续严格下降。
for i+1 < n && arr[i] > arr[i+1] {
i++
}
// 只有恰好走到末尾，才说明中间没有平台或二次上升。
return i == n-1
}
复杂度分析
- 时间复杂度：$O(n)$，两个阶段合计单向扫描。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 严格比较自动排除平台。
- 峰顶不能在两端，保证两种坡都存在。
- 最后必须走完整个数组，不能只找到局部山峰。
易错点总结
[!yellow]
- 上升或下降条件不能带等号，否则会把平台当成合法山坡。
- 只找到一次下降就返回成功，会漏查后面的再次上升或平台。
- 比较相邻项前先检查
i+1<n，避免在末尾越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 845. 数组中的最长山脉 | 中等 | 原题在任意区间找最长山脉，本题要求整个数组都满足先严格升后严格降。 |
| 852. 山脉数组的峰顶索引 | 中等 | 原题已保证是山脉，只需定位峰，本题必须验证两侧都非空且没有平坡。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！