LeetCode 941. 有效的山脉数组

2021-06-10 HGNULB 约 9 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 941. 有效的山脉数组

题意分析

给一个整数数组 arr，判断它是不是「山脉数组」：存在一个下标 i（0 < i < n - 1），使得 arr[0] < arr[1] < ... < arr[i] 且 arr[i] > arr[i+1] > ... > arr[n-1]。是就返回 true，否则 false。

定义里藏着三个必须同时满足的条件，缺一不可。第一，整个数组恰好由「一段严格上升」和「一段严格下降」拼成；第二，全程是严格不等号，任何位置出现相等都直接出局；第三，峰顶下标 i 被限制在 0 < i < n - 1，也就是上坡和下坡都必须真实存在，纯递增或纯递减都不算山脉。由此立刻可得 n < 3 必然返回 false。

约束里 n 最大 $10^4$、元素值最大 $10^4$，规模小到几乎不构成限制，说明本题考的不是效率而是分类是否完备——它是一道边界题，不是算法题。既然只是判断形状，就没有必要排序、二分或者建任何辅助结构，一次线性扫描把形状「走」出来即可。

特别注意元素值范围里允许出现重复值，而定义要求严格单调，所以像 [1,2,2,1] 这种看起来很像山的输入是非法的。这类「看着像但不合法」的用例正是本题的主要陷阱。

还有一个隐含的边界：题目没有说数组一定非空，[]、[0]、[0,1]、[3,5,5] 都可能出现，处理逻辑必须能自然覆盖它们，而不是靠零散的特判打补丁。

解法：双指针上坡/下坡扫描

核心思路

暴力的想法是：先枚举峰顶下标 i，再分别验证 [0, i] 严格递增、[i, n-1] 严格递减。这在 $O(n^2)$ 下能过，但白白做了重复功——因为峰顶其实不需要枚举，它是被数据唯一确定的。

瓶颈在于「峰顶未知」这个假设本身是多余的。观察：如果从下标 0 出发，只要 arr[i] < arr[i+1] 成立就一直往右走，那么停下来的位置就是第一个不再上升的位置。而山脉数组的形状保证了这个位置只可能是峰顶——因为在峰顶之前每一步都严格上升，走到峰顶后 arr[i] > arr[i+1] 立刻中止。于是峰顶可以在 $O(n)$ 内一次性定位，不需要枚举。

记指针为 i。第一阶段的不变量是：循环每退出一次迭代，都保证 arr[0] < arr[1] < ... < arr[i] 严格成立；循环终止时，要么 i == n - 1（走到了末尾），要么 arr[i] >= arr[i+1]（遇到了平台或下坡）。

第二阶段从同一个 i 继续，只要 arr[i] > arr[i+1] 就继续走，不变量是：arr[peak] > ... > arr[i] 严格成立。终止时要么走到末尾，要么遇到平台或上坡。

现在把三个条件逐一映射到这两阶段的终止状态上：

上坡必须非空 ⇔ 第一阶段结束时 i != 0；

下坡必须非空 ⇔ 第一阶段结束时 i != n - 1（否则从头升到尾，没有下坡）；

中间不能有平台或二次上升 ⇔ 第二阶段结束时恰好 i == n - 1。

这三个检查合在一起既充分又必要：严格性由两个循环条件里的 < 和 > 保证（相等时循环不会前进），完整性由最终 i == n - 1 保证（任何提前停下都说明中间出现了非法形状）。因此只需两趟扫描加三次判断，不需要任何额外分类。

解题步骤

先挡掉 n < 3：山脉至少要「升一步 + 降一步」，最少三个元素。为什么要显式写：后面要访问 arr[0] 和 arr[n-1] 并做 i == n - 1 比较，先挡掉小数组能让后续逻辑不必再操心长度。

上坡阶段：i = 0，当 i + 1 < n && arr[i] < arr[i+1] 时 i++。为什么循环条件带 i + 1 < n：arr[i+1] 的访问必须在合法范围内，否则走到末尾会越界。为什么用严格 <：遇到相等时循环立刻停住，把「平台」交给后面的检查判死，这正是严格单调要求的落点。

检查峰顶合法：若 i == 0 返回 false，说明一开始就没上升（首元素不小于次元素），没有左坡；若 i == n - 1 返回 false，说明一路升到底，没有右坡。为什么两个都要查：它们分别对应定义里 i > 0 和 i < n - 1 两个约束，漏掉任何一个都会把纯递增或纯递减的数组误判为山脉。

下坡阶段：继续用同一个 i，当 i + 1 < n && arr[i] > arr[i+1] 时 i++。为什么复用 i 而不是新开指针：第一阶段已经把 i 停在峰顶，从峰顶继续往下走天然衔接，也省掉一个变量。

最终判定：返回 i == n - 1。为什么这一条就够：若中途遇到相等或再次上升，第二阶段会提前停住，i 到不了末尾；能走到末尾就说明整段下坡严格成立，配合前两个检查，三个条件全部满足。

以 arr = [0, 3, 2, 1] 走一遍。n = 4，通过长度检查。
上坡阶段：i = 0，arr[0]=0 < arr[1]=3，i 变 1；arr[1]=3 < arr[2]=2 不成立，停在 i = 1。
峰顶检查：i 既不是 0 也不是 n - 1 = 3，通过，峰顶就是下标 1、值 3。
下坡阶段：arr[1]=3 > arr[2]=2，i 变 2；arr[2]=2 > arr[3]=1，i 变 3；此时 i + 1 = 4 不小于 n，循环结束。
最终判定：i == 3 == n - 1，返回 true。

再看反例 arr = [3, 5, 5]。长度过关；上坡阶段 3 < 5 让 i 走到 1，再比 arr[1]=5 < arr[2]=5 不成立而停住；峰顶检查通过（i = 1，非首非尾）；下坡阶段 arr[1]=5 > arr[2]=5 不成立，i 原地不动；最终 i = 1 != 2，返回 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)$。凭什么：指针 i 只会单向递增、从不回退，两个循环合起来最多把 i 从 0 推到 n - 1，每次推进只做一次比较，因此总操作数与 n 同阶。

空间复杂度：$O(1)$。凭什么：只用了 n 和 i 两个整型变量，没有复制数组也没有开辅助结构，占用与输入规模无关。

关键点总结

「严格单调」在代码里的唯一落点就是比较符不带等号：用 < 和 > 会让指针在相等处自动卡住，把平台交给后续检查判死，这比显式写 if (arr[i] == arr[i+1]) return false 更简洁也更不易漏。

用「走到哪里停下」代替「枚举分割点」，是单调形状判定题的通用降维手法：只要形状唯一确定，分割点就不必枚举。

循环条件里的 i + 1 < n 与循环体里的 arr[i+1] 必须成对出现，凡是访问相邻元素的扫描都要先确认右边界。

把题目定义的每个约束显式对应到代码中的一处检查（左坡非空 → i != 0，右坡非空 → i != n-1，无平台 → 末尾判定），是边界题不漏条件的可靠做法。

面试视角：这道题面试官不看你写得多快，而是看你能否主动报出边界用例。写完后直接口述 []、[0,1]、[3,5,5]、[0,1,2,3]、[3,2,1,0]、[2,1] 六组用例并说明各自走到哪一步被拒，比多写一个解法更有说服力。

同样的两阶段扫描骨架可以直接改造成「求最长山脉」「统计山脉个数」，区别只在于把布尔判定换成计数与最值维护。

易错点总结

错误写法：上坡循环用 arr[i] <= arr[i+1] → 用例 [3,5,5,1] 会越过平台把峰顶定到下标 2，随后下坡成立返回 true，但正确答案是 false。

错误写法：下坡循环用 arr[i] >= arr[i+1] → 用例 [1,3,2,2] 会一路走到末尾返回 true，但末尾存在平台，正确答案是 false。

错误写法：漏掉 i == 0 的检查 → 用例 [3,2,1] 里上坡一步没走，i 停在 0，下坡直接走到末尾，返回 true，而纯递减不是山脉。

错误写法：漏掉 i == n - 1 的检查 → 用例 [0,1,2,3] 里一路升到尾，第二个循环不执行，最终 i == n - 1 判定为 true，而纯递增不是山脉。

错误写法：漏掉 n < 3 的前置判断 → 用例 [] 在 Java 里 n - 1 = -1，i == 0 恰好成立侥幸返回 false，但用例 [1] 时 i == 0 == n - 1 也返回 false 属于蒙对；一旦有人把两个检查改写成访问 arr[n-1]，空数组立刻越界。

错误写法：循环条件写成 i < n 而在体内访问 arr[i+1] → 用例 [0,1,2] 在 i = 2 时读 arr[3]，Java 抛数组越界，Go 直接 panic。

错误写法：下坡阶段另起一个从 n - 1 向左走的指针，最后判断两指针是否相遇 → 用例 [1,2,2,1] 中左指针停在 1、右指针停在 2，二者不等确实返回 false，但用例 [0,2,2,2,0] 里左停 1 右停 3，若代码写成「相遇或相邻即通过」就会误判为 true。

错误写法：先判断峰顶再判断长度，顺序颠倒 → 用例 [] 时先执行 i == n - 1 与 n = 0 的比较，逻辑虽不崩但语义混乱，一旦后续改动引入 arr[i] 访问就会崩。

错误写法：把返回值写成 i >= n - 1 → 用例上没有区别，但一旦第二个循环因边界写错让 i 越过 n - 1，这个宽松判定会掩盖越界 bug，使非法输入被判为 true。

错误写法：用「先找最大值下标当峰顶」代替扫描 → 用例 [1,3,3,1] 里最大值有两个下标，取到哪个都无法反映平台非法，需要额外判重复才能补救。

相似题目

题目	难度	考察点
852. 山脉数组的峰顶索引	中等	已保证是山脉，只求峰顶下标，可用二分把 $O(n)$ 压到 $O(\log n)$
845. 数组中的最长山脉	中等	从「整体是否为山」变成「找最长子数组山」，需枚举峰顶双向扩展
1095. 山脉数组中查找目标值	困难	三次二分：先找峰顶，再在升段与降段分别二分，且访问次数受限
162. 寻找峰值	中等	只保证相邻不等而非全局山形，二分靠的是「往高处走必有峰」
1671. 得到山形数组的最少删除次数	困难	转成双向最长上升子序列，考的是 LIS 而不是扫描