Medium

题目描述

我们把数组 arr 中符合下列属性的子数组称为 山脉：

  • arr.length >= 3
  • 存在某个下标 i（0 < i < arr.length - 1）使得：
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你由整数组成的数组 arr，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

示例 1：

输入：arr = [2,1,4,7,3,2,5]
输出：5
解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。

示例 2：

输入：arr = [2,2,2]
输出：0
解释：不含 "山脉"。

提示：

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^4

进阶：

  • 你可以仅用一趟扫描解决这个问题吗？
  • 你可以用 O(1) 空间解决这个问题吗？

解题思路

这道题要求找出数组中最长的山脉子数组。山脉必须满足先严格递增再严格递减的条件。

解法一：暴力枚举（O(n²)） 对每个可能的山顶位置，向两边扩展找出最长的上升和下降序列。

解法二：动态规划（O(n)） 预处理每个位置能向左扩展的上升长度和向右扩展的下降长度，然后枚举山顶。

解法三：一次遍历（推荐） 这是最优解法，时间复杂度O(n)，空间复杂度O(1)。核心思想是：

  1. 遍历数组，寻找上升序列的起点
  2. 从起点开始，统计连续上升的长度
  3. 如果找到下降点，继续统计连续下降的长度
  4. 如果同时存在上升和下降部分，就构成了一个山脉

关键是要确保山脉必须同时包含上升和下降两个部分，且长度至少为3。每当找到一个完整的山脉后，需要重新开始寻找下一个山脉的起点。

代码实现

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        if (n < 3) return 0;
        
        int maxLen = 0;
        int i = 0;
        
        while (i < n - 1) {
            // 跳过相等或递减的元素，寻找上升序列的起点
            while (i < n - 1 && arr[i] >= arr[i + 1]) {
                i++;
            }
            
            if (i >= n - 1) break;
            
            // 统计上升序列的长度
            int up = 0;
            while (i < n - 1 && arr[i] < arr[i + 1]) {
                up++;
                i++;
            }
            
            // 统计下降序列的长度
            int down = 0;
            while (i < n - 1 && arr[i] > arr[i + 1]) {
                down++;
                i++;
            }
            
            // 如果同时存在上升和下降，更新最大长度
            if (up > 0 && down > 0) {
                maxLen = max(maxLen, up + down + 1);
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        if n < 3:
            return 0
        
        max_len = 0
        i = 0
        
        while i < n - 1:
            # 跳过相等或递减的元素，寻找上升序列的起点
            while i < n - 1 and arr[i] >= arr[i + 1]:
                i += 1
            
            if i >= n - 1:
                break
            
            # 统计上升序列的长度
            up = 0
            while i < n - 1 and arr[i] < arr[i + 1]:
                up += 1
                i += 1
            
            # 统计下降序列的长度
            down = 0
            while i < n - 1 and arr[i] > arr[i + 1]:
                down += 1
                i += 1
            
            # 如果同时存在上升和下降，更新最大长度
            if up > 0 and down > 0:
                max_len = max(max_len, up + down + 1)
        
        return max_len

public class Solution {
    public int LongestMountain(int[] arr) {
        int n = arr.Length;
        if (n < 3) return 0;
        
        int maxLen = 0;
        int i = 0;
        
        while (i < n - 1) {
            // 跳过相等或递减的元素，寻找上升序列的起点
            while (i < n - 1 && arr[i] >= arr[i + 1]) {
                i++;
            }
            
            if (i >= n - 1) break;
            
            // 统计上升序列的长度
            int up = 0;
            while (i < n - 1 && arr[i] < arr[i + 1]) {
                up++;
                i++;
            }
            
            // 统计下降序列的长度
            int down = 0;
            while (i < n - 1 && arr[i] > arr[i + 1]) {
                down++;
                i++;
            }
            
            // 如果同时存在上升和下降，更新最大长度
            if (up > 0 && down > 0) {
                maxLen = Math.Max(maxLen, up + down + 1);
            }
        }
        
        return maxLen;
    }
}

var longestMountain = function(arr) {
    const n = arr.length;
    if (n < 3) return 0;
    
    let maxLen = 0;
    let i = 0;
    
    while (i < n - 1) {
        // 跳过相等或递减的元素，寻找上升序列的起点
        while (i < n - 1 && arr[i] >= arr[i + 1]) {
            i++;
        }
        
        if (i >= n - 1) break;
        
        // 统计上升序列的长度
        let up = 0;
        while (i < n - 1 && arr[i] < arr[i + 1]) {
            up++;
            i++;
        }
        
        // 统计下降序列的长度
        let down = 0;
        while (i < n - 1 && arr[i] > arr[i + 1]) {
            down++;
            i++;
        }
        
        // 如果同时存在上升和下降，更新最大长度
        if (up > 0 && down > 0) {
            maxLen = Math.max(maxLen, up + down + 1);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多被访问常数次
空间复杂度O(1)只使用了几个变量存储状态

相关题目