Easy

题目描述

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：

  • arr.length >= 3
  • 在 0 < i < arr.length - 1 条件下，存在 i 使得：
    • arr[0] < arr[1] < ... < arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

示例 1：

输入：arr = [2,1]
输出：false

示例 2：

输入：arr = [3,5,5]
输出：false

示例 3：

输入：arr = [0,3,2,1]
输出：true

提示：

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

解题思路

解题思路

这道题要求判断一个数组是否为有效的山脉数组。山脉数组的特点是先严格递增，然后严格递减，且至少有3个元素。

方法一：双指针法（推荐）

使用两个指针分别从数组两端向中间移动：

  1. 左指针从左向右，找到递增序列的终点
  2. 右指针从右向左，找到递减序列的起点
  3. 判断两个指针是否在同一位置相遇，且都有移动过

方法二：一次遍历法

遍历数组，记录当前状态（上升/下降），检查是否符合山脉特征：

  1. 首先必须是上升阶段
  2. 遇到下降后不能再上升
  3. 不能有相等元素

方法三：状态机法

使用状态机来追踪当前处于上升还是下降阶段，确保状态转换的合法性。

双指针法最直观且高效，时间复杂度O(n)，空间复杂度O(1)。核心思想是分别找到上升和下降的边界，然后检查它们是否正确连接形成山脉。

代码实现

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        int n = arr.size();
        if (n < 3) return false;
        
        int left = 0, right = n - 1;
        
        // 从左向右找到上升序列的终点
        while (left < n - 1 && arr[left] < arr[left + 1]) {
            left++;
        }
        
        // 从右向左找到下降序列的起点
        while (right > 0 && arr[right - 1] > arr[right]) {
            right--;
        }
        
        // 检查是否在同一点相遇，且都有移动过
        return left == right && left > 0 && right < n - 1;
    }
};

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        n = len(arr)
        if n < 3:
            return False
        
        left, right = 0, n - 1
        
        # 从左向右找到上升序列的终点
        while left < n - 1 and arr[left] < arr[left + 1]:
            left += 1
        
        # 从右向左找到下降序列的起点
        while right > 0 and arr[right - 1] > arr[right]:
            right -= 1
        
        # 检查是否在同一点相遇，且都有移动过
        return left == right and left > 0 and right < n - 1

public class Solution {
    public bool ValidMountainArray(int[] arr) {
        int n = arr.Length;
        if (n < 3) return false;
        
        int left = 0, right = n - 1;
        
        // 从左向右找到上升序列的终点
        while (left < n - 1 && arr[left] < arr[left + 1]) {
            left++;
        }
        
        // 从右向左找到下降序列的起点
        while (right > 0 && arr[right - 1] > arr[right]) {
            right--;
        }
        
        // 检查是否在同一点相遇，且都有移动过
        return left == right && left > 0 && right < n - 1;
    }
}

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function(arr) {
    if (arr.length < 3) return false;
    
    let i = 0;
    
    // Walk up
    while (i < arr.length - 1 && arr[i] < arr[i + 1]) {
        i++;
    }
    
    // Peak cannot be first or last element
    if (i === 0 || i === arr.length - 1) return false;
    
    // Walk down
    while (i < arr.length - 1 && arr[i] > arr[i + 1]) {
        i++;
    }
    
    return i === arr.length - 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
双指针法O(n)O(1)
一次遍历法O(n)O(1)
状态机法O(n)O(1)

其中 n 为数组长度。所有方法都只需要常数额外空间，时间复杂度都是线性的，但双指针法在实现上最简洁明了。

相关题目