LeetCode 845. 数组中的最长山脉

Categories:

题目描述
思路分析
1. 解法一：上升/下降数组（推荐）
相似题目

题目描述

✅ 845. 数组中的最长山脉

思路分析

解法一：上升/下降数组（推荐）

核心思路：

用 up[i] 表示以 i 结尾的连续上升长度。

用 down[i] 表示以 i 开始的连续下降长度。

当 up[i] > 0 且 down[i] > 0 时，i 为山顶，长度为 up[i] + down[i] + 1。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于 up/down 数组。

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return 0;
        }

        int[] up = new int[n];
        int[] down = new int[n];

        // 计算每个位置向左的上升长度
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                up[i] = up[i - 1] + 1;
            }
        }

        // 计算每个位置向右的下降长度
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                down[i] = down[i + 1] + 1;
            }
        }

        int ans = 0;
        // 枚举山顶计算最大长度
        for (int i = 1; i < n - 1; i++) {
            if (up[i] > 0 && down[i] > 0) {
                ans = Math.max(ans, up[i] + down[i] + 1);
            }
        }

        return ans;
    }
}

func longestMountain(arr []int) int {
	n := len(arr)
	if n < 3 {
		return 0
	}

	up := make([]int, n)
	down := make([]int, n)

	// 计算每个位置向左的上升长度
	for i := 1; i < n; i++ {
		if arr[i] > arr[i-1] {
			up[i] = up[i-1] + 1
		}
	}

	// 计算每个位置向右的下降长度
	for i := n - 2; i >= 0; i-- {
		if arr[i] > arr[i+1] {
			down[i] = down[i+1] + 1
		}
	}

	ans := 0
	// 枚举山顶计算最大长度
	for i := 1; i < n-1; i++ {
		if up[i] > 0 && down[i] > 0 {
			length := up[i] + down[i] + 1
			if length > ans {
				ans = length
			}
		}
	}

	return ans
}

相似题目

题目	难度	考察点
674. 最长连续递增序列	简单	数组扫描
300. 最长递增子序列	中等	动态规划
941. 有效的山脉数组	简单	双指针
162. 寻找峰值	中等	二分
852. 山脉数组的峰顶索引	简单	二分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/16670802