LeetCode 845. 数组中的最长山脉

约 5 分钟
文章信息 10 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 美团 快手 拼多多
标签
数组 动态规划 双指针 枚举
目录

题目描述

✅ 845. 数组中的最长山脉

题意分析

在一个整数数组里找最长的一段连续子数组，它必须先一路严格上升，到某个位置后一路严格下降。返回这段的长度，找不到就返回 0。

「连续子数组」而不是子序列，说明只能在原数组上取一段区间，不能跳着挑元素。这直接排除了动态规划里那些允许跳跃的写法。

「严格」是最容易被忽略的约束信号：上升段里不能出现相等，下降段里也不能出现相等。也就是说一旦碰到 arr[i] == arr[i+1]，这个位置就是一道墙，任何山脉都跨不过去。

另一个隐含要求是上升段和下降段都必须非空，所以合法山脉的长度至少是 3，形如 低 高 低。只上升不下降或者只下降不上升都不算。

边界情况包括：数组长度不足 3；整个数组单调；存在连续相等的平台；最大值出现在数组首尾（这种位置不可能当峰顶，因为它缺一侧）；以及两个山脉紧挨着共用一个谷底。

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

核心思路

合法山脉由一段非空的严格上升坡和紧随其后的一段非空的严格下降坡组成。与其枚举峰顶后再向两边重复扩展，不如让一个指针直接消费连续斜坡：先跳过平台，再数上升边数 up，最后数下降边数 down。

每轮结束时，指针已经走到当前下降坡之后；若 up > 0 && down > 0，刚消费的区间就是完整山脉，长度为边数之和再加一个节点，即 up + down + 1。

循环不变量是：进入每一轮时，指针左侧的相邻关系都已归入某个最大连续坡段，不会再次参与旧山脉；本轮只向右移动并消费“平台—上升—下降”。因此每条相邻边只被检查常数次，且任何合法山脉都会在其上升起点处被完整统计。

严格性决定了相等元素是分界线：平台不能属于任何山脉，必须先跳过。只上升或只下降也不能更新答案，因为峰顶两侧都必须存在。

解题步骤

  1. 令 index = 1，它表示正在比较 arr[index - 1] 与 arr[index]。
  2. 先跳过所有相等的相邻元素，平台不能跨越。
  3. 连续满足 arr[index] > arr[index - 1] 时递增 up 并右移。
  4. 随后连续满足 arr[index] < arr[index - 1] 时递增 down 并右移。
  5. 只有 up、down 都大于 0 时，用 up + down + 1 更新答案。

对 [2,1,4,7,3,2,5]，第一轮只消费下降边 2 > 1，不构成山脉；下一轮消费两条上升边 1 < 4 < 7 和两条下降边 7 > 3 > 2，得到长度 5。最后的 2 < 5 没有下降坡，不更新答案。

代码实现

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
}

复杂度分析

  • 时间复杂度：$O(n)$。扫描下标只向右移动，每对相邻元素只被比较常数次。
  • 空间复杂度：$O(1)$。

关键点总结

  • 山脉长度等于上升边数、下降边数之和再加 1。
  • up > 0 && down > 0 同时保证峰顶两侧都存在。
  • 相等元素既不属于上升也不属于下降，是必须跳过的硬边界。
  • 指针停在谷底后的第一个位置；这个谷底仍可作为下一座山的起点。
  • 面试时可用“消费最大连续坡段”的不变量解释线性复杂度，而不是只说双指针。

易错点总结

  • 使用非严格比较，会把 [1,2,2,1] 的平台误算成山脉。
  • 只判断 up + down > 0，会把纯递增或纯递减数组计入答案。
  • 把长度写成 up + down，会少算峰顶或起点这个节点。
  • 遇到平台不移动指针，会在全相等数组上死循环。
  • 数组长度小于 3 时答案应自然保持 0，不要预设最短长度为 3。

相似题目

题目 难度 考察点
852. 山脉数组的峰顶索引 中等 二分定位峰顶
941. 有效的山脉数组 简单 单趟双向验证
1095. 山脉数组中查找目标值 困难 交互式接口下的二分
1671. 得到山形数组的最少删除次数 困难 双向最长递增子序列
300. 最长递增子序列 中等 单向递增的子序列长度