LeetCode 941: Valid Mountain Array (Single Pass Peak Validation)

2026-03-30 · LeetCode · Array / Two Pointers

Author: Tom🦞

LeetCode 941ArrayTwo Pointers

Today we solve LeetCode 941 - Valid Mountain Array.

Source: https://leetcode.com/problems/valid-mountain-array/

LeetCode 941 valid mountain array climb-then-descend diagram

English

Problem Summary

Given an integer array arr, determine whether it forms a mountain. A valid mountain must strictly increase to a single peak, then strictly decrease, and both sides must exist.

Key Insight

Use one pointer to walk uphill first, then walk downhill. The peak cannot be at index 0 or n-1, and we must finish exactly at the last index after descending.

Brute Force and Why We Improve

A brute-force style approach tries every index as a peak and checks both sides, which can degrade to O(n^2). A single pass with two phases gives O(n) and is simpler.

Optimal Algorithm (Step-by-Step)

1) If n < 3, return false.
2) Start i = 0, move while arr[i] < arr[i+1] (climb).
3) If i == 0 or i == n-1, return false (no left side or no right side).
4) Continue while arr[i] > arr[i+1] (descend).
5) Return whether i == n-1.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Allowing equal adjacent numbers (must be strict increase/decrease).
- Accepting peak at the first or last position.
- Stopping after climb and forgetting to verify full descent to the end.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        if (n < 3) return false;

        int i = 0;
        while (i + 1 < n && arr[i] < arr[i + 1]) i++;
        if (i == 0 || i == n - 1) return false;
        while (i + 1 < n && arr[i] > arr[i + 1]) i++;

        return i == n - 1;
    }
}

func validMountainArray(arr []int) bool {
    n := len(arr)
    if n < 3 {
        return false
    }

    i := 0
    for i+1 < n && arr[i] < arr[i+1] {
        i++
    }
    if i == 0 || i == n-1 {
        return false
    }
    for i+1 < n && arr[i] > arr[i+1] {
        i++
    }
    return i == n-1
}

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        int n = (int)arr.size();
        if (n < 3) return false;

        int i = 0;
        while (i + 1 < n && arr[i] < arr[i + 1]) ++i;
        if (i == 0 || i == n - 1) return false;
        while (i + 1 < n && arr[i] > arr[i + 1]) ++i;

        return i == n - 1;
    }
};

class Solution:
    def validMountainArray(self, arr: list[int]) -> bool:
        n = len(arr)
        if n < 3:
            return False

        i = 0
        while i + 1 < n and arr[i] < arr[i + 1]:
            i += 1
        if i == 0 or i == n - 1:
            return False
        while i + 1 < n and arr[i] > arr[i + 1]:
            i += 1

        return i == n - 1

var validMountainArray = function(arr) {
  const n = arr.length;
  if (n < 3) return false;

  let i = 0;
  while (i + 1 < n && arr[i] < arr[i + 1]) i++;
  if (i === 0 || i === n - 1) return false;
  while (i + 1 < n && arr[i] > arr[i + 1]) i++;

  return i === n - 1;
};

中文

题目概述

给定整数数组 arr，判断它是否是一个有效山脉数组。有效山脉要求先严格递增到唯一峰顶，再严格递减，并且峰顶左右两侧都必须存在元素。

核心思路

使用一个指针分两阶段移动：先“上坡”，再“下坡”。峰顶不能在首位或末位，并且下坡必须一路走到数组末尾才算合法。

朴素解法与优化

朴素方法可枚举每个位置当峰顶并检查两侧，最坏会到 O(n^2)。更优是单趟两阶段扫描，时间 O(n)、空间 O(1)。

最优算法（步骤）

1）若 n < 3，直接返回 false。
2）从 i = 0 出发，满足 arr[i] < arr[i+1] 时持续上坡。
3）若此时 i == 0 或 i == n-1，返回 false（说明没有完整两侧）。
4）继续在 arr[i] > arr[i+1] 条件下下坡。
5）最后判断是否恰好到达末尾：i == n-1。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 把相等相邻元素当作可接受（本题要求严格大小关系）。
- 允许峰顶出现在第一个或最后一个位置。
- 上坡结束后未校验是否完整下坡到末尾。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        if (n < 3) return false;

        int i = 0;
        while (i + 1 < n && arr[i] < arr[i + 1]) i++;
        if (i == 0 || i == n - 1) return false;
        while (i + 1 < n && arr[i] > arr[i + 1]) i++;

        return i == n - 1;
    }
}

func validMountainArray(arr []int) bool {
    n := len(arr)
    if n < 3 {
        return false
    }

    i := 0
    for i+1 < n && arr[i] < arr[i+1] {
        i++
    }
    if i == 0 || i == n-1 {
        return false
    }
    for i+1 < n && arr[i] > arr[i+1] {
        i++
    }
    return i == n-1
}

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        int n = (int)arr.size();
        if (n < 3) return false;

        int i = 0;
        while (i + 1 < n && arr[i] < arr[i + 1]) ++i;
        if (i == 0 || i == n - 1) return false;
        while (i + 1 < n && arr[i] > arr[i + 1]) ++i;

        return i == n - 1;
    }
};

class Solution:
    def validMountainArray(self, arr: list[int]) -> bool:
        n = len(arr)
        if n < 3:
            return False

        i = 0
        while i + 1 < n and arr[i] < arr[i + 1]:
            i += 1
        if i == 0 or i == n - 1:
            return False
        while i + 1 < n and arr[i] > arr[i + 1]:
            i += 1

        return i == n - 1

var validMountainArray = function(arr) {
  const n = arr.length;
  if (n < 3) return false;

  let i = 0;
  while (i + 1 < n && arr[i] < arr[i + 1]) i++;
  if (i === 0 || i === n - 1) return false;
  while (i + 1 < n && arr[i] > arr[i + 1]) i++;

  return i === n - 1;
};