LeetCode 845. 数组中的最长山脉

2026-05-11 HGNULB 约 5 分钟

文章信息 10 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节微软美团拼多多快手

题目描述

✅ 845. 数组中的最长山脉

题意分析

在数组中找出最长的连续山脉子数组，返回其中的元素数量；不存在时返回 0。山脉必须先严格上升、再严格下降，峰顶不能位于两端，所以两侧至少各有一条变化边。

相等的相邻元素形成平台，不能跨越平台构成同一座山脉。纯递增、纯递减或不足三个元素的区间都不符合要求；只需要返回最大长度，不需要返回具体区间。

解法：一次扫描统计连续坡长

核心思路

[!blue]

一座山脉由一段连续上坡和紧随其后的一段连续下坡构成。固定峰顶时，把两侧延伸到严格趋势停止的位置就得到包含该峰的最长山脉，因此可以依次扫描完整坡段，不必枚举所有子数组起点和终点。

令 index 表示下一条待比较的相邻关系，即比较 arr[index - 1] 和 arr[index]。每轮先跳过相等关系，再统计连续上升边数 up，随后统计连续下降边数 down。只有 up > 0 且 down > 0 才形成山脉；边数之和比元素数少一，所以长度为 up + down + 1。

初始下降段可以被直接跳过，因为它前面没有上坡，不能以此形成完整山脉。上坡如果被平台中断，本轮没有下坡，也不计入；下一轮会跳过平台，从后面重新寻找完整坡段。

下降结束后，若接下来重新上升，刚到达的谷底仍位于 arr[index - 1]，下一轮能从同一个谷底开始统计新上坡。不能再无条件增加一次 index，否则会跳过下一座山的第一条上升边。

每个完整上坡最多对应一个紧随其后的完整下坡，扫描会覆盖所有可能的峰；没有必要从坡段内部再重复出发，因为缩短任何一侧都不会获得更长山脉。所有内层循环共享只向右的下标，总工作量仍为线性。

解题步骤

初始化答案为 0，令 index = 1，从第一对相邻元素开始比较。

跳过连续相等的相邻关系，把平台视为山脉边界。

连续上升时累加 up 并右移下标，再连续下降时累加 down 并右移。

两种边都存在时，用 up + down + 1 更新最长长度。

从当前未处理关系继续下一轮，直到数组末尾。

代码实现

class Solution {
    public int longestMountain(int[] arr) {
        int answer = 0;
        int index = 1;

        while (index < arr.length) {
            // 平台不属于上坡或下坡，先推进避免在此停滞。
            while (index < arr.length && arr[index] == arr[index - 1]) {
                index++;
            }

            int up = 0;

            while (index < arr.length && arr[index] > arr[index - 1]) {
                up++;
                index++;
            }

            int down = 0;

            while (index < arr.length && arr[index] < arr[index - 1]) {
                down++;
                index++;
            }

            // 两侧都有边才是山脉，元素数比两侧边数之和多一。
            if (up > 0 && down > 0) {
                answer = Math.max(answer, up + down + 1);
            }
        }

        return answer;
    }
}

func longestMountain(arr []int) int {
    answer, index := 0, 1

    for index < len(arr) {
        // 平台不属于上坡或下坡，先推进避免在此停滞。
        for index < len(arr) && arr[index] == arr[index-1] {
            index++
        }

        up := 0
        for index < len(arr) && arr[index] > arr[index-1] {
            up++
            index++
        }

        down := 0
        for index < len(arr) && arr[index] < arr[index-1] {
            down++
            index++
        }

        // 两侧都有边才是山脉，元素数比两侧边数之和多一。
        if up > 0 && down > 0 && up+down+1 > answer {
            answer = up + down + 1
        }
    }
    return answer
}

复杂度分析

设数组长度为 $n$。

时间复杂度：$O(n)$。下标只向右，每条相邻关系只被检查常数次。

空间复杂度：$O(1)$，只维护扫描位置、坡长和答案。

关键点总结

[!green]

统计的是上升边和下降边，山脉元素数还需要加一。

两侧必须都非空，平台会切断严格变化趋势。

下一轮保留谷底作为可能起点，避免遗漏相邻山脉。

共享单向下标使多个循环合计仍然只扫描一次数组。

易错点总结

[!yellow]

使用非严格比较会把平台并入山脉，应分别使用 >、<。

只检查总坡长非零会接受纯上坡或纯下坡，必须同时满足 up > 0、down > 0。

长度不能只写 up + down，边数与节点数相差一。

平台既不进入上坡循环也不进入下坡循环，必须单独推进，否则可能停在原位置。

每轮结束额外推进下标会丢掉谷底后的第一条边；短数组则让答案自然保持零即可。

相似题目

题目	难度	关联与区别
852. 山脉数组的峰顶索引	中等	原题保证整个输入是一座山，只需找峰，本题要同时定位峰两侧的上升下降段并取最长。
941. 有效的山脉数组	简单	原题验证整个数组是否为山脉，本题在任意局部区间寻找最长山脉。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/16670802

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！