LeetCode 852: Peak Index in a Mountain Array (Binary Search on Slope Direction)

2026-03-30 · LeetCode · Binary Search / Array
Author: Tom🦞
LeetCode 852Binary SearchArrayMountain Array

Today we solve LeetCode 852 - Peak Index in a Mountain Array.

Source: https://leetcode.com/problems/peak-index-in-a-mountain-array/

LeetCode 852 binary search on mountain slope diagram

English

Problem Summary

You are given a mountain array arr, which strictly increases up to one peak and then strictly decreases. Return the index of that peak element.

Key Insight

At any index mid, compare arr[mid] with arr[mid + 1]. If arr[mid] < arr[mid + 1], you are on the rising slope so the peak is to the right. Otherwise, you are on the falling slope (or at peak), so the peak is at mid or to the left.

Brute Force and Limitations

A linear scan can find the first index where arr[i] > arr[i+1], which is O(n). It works but does not use the mountain structure optimally.

Optimal Algorithm Steps

1) Set left = 0, right = n - 1.
2) While left < right, compute mid.
3) If arr[mid] < arr[mid+1], move left = mid + 1.
4) Else move right = mid.
5) Loop ends at the peak index left.

Complexity Analysis

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

Common Pitfalls

- Using right = mid - 1 on descending side may skip the real peak.
- Forgetting mid + 1 boundary safety (the left < right loop condition keeps it valid).
- Treating this as generic local maxima search without mountain constraints.

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

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
func peakIndexInMountainArray(arr []int) int {
    left, right := 0, len(arr)-1
    for left < right {
        mid := left + (right-left)/2
        if arr[mid] < arr[mid+1] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = (int)arr.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1
        while left < right:
            mid = left + (right - left) // 2
            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left
var peakIndexInMountainArray = function(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < arr[mid + 1]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
};

中文

题目概述

给定一个山脉数组 arr：先严格递增后严格递减。请返回峰顶元素的下标。

核心思路

比较 arr[mid] 与 arr[mid+1]：如果前者更小，说明还在上坡，峰顶在右侧；否则已经到下坡或正好在峰顶，峰顶在 mid 或其左侧。这个性质天然适合二分。

暴力解法与不足

线性扫描找到第一个满足 arr[i] > arr[i+1] 的位置即可，复杂度 O(n)。虽然正确，但没有利用山脉数组的单峰结构。

最优算法步骤

1）初始化 left = 0，right = n - 1。
2）当 left < right 时取 mid。
3）若 arr[mid] < arr[mid+1]，说明在上坡，令 left = mid + 1。
4）否则令 right = mid。
5）循环结束时 left 即峰顶下标。

复杂度分析

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

常见陷阱

- 在下坡分支写成 right = mid - 1 可能跳过真实峰顶。
- 忽略 mid + 1 越界风险（使用 left < right 条件即可保证安全）。
- 把题目当成普通“局部极大值”问题，丢失山脉数组前提。

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

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
func peakIndexInMountainArray(arr []int) int {
    left, right := 0, len(arr)-1
    for left < right {
        mid := left + (right-left)/2
        if arr[mid] < arr[mid+1] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = (int)arr.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1
        while left < right:
            mid = left + (right - left) // 2
            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left
var peakIndexInMountainArray = function(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < arr[mid + 1]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
};

Comments