Medium

题目描述

给你由整数组成的山脉数组 arr，长度为 n，其中的值递增到一个峰值元素然后递减。

返回峰值元素的索引。

你的任务是用 O(log(n)) 时间复杂度来解决此问题。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

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

示例 3：

输入：arr = [0,10,5,2]
输出：1

提示：

  • 3 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^6
  • 题目数据保证 arr 是一个山脉数组

解题思路

解题思路

这是一道典型的二分查找问题。由于题目保证了数组是山脉数组（先递增后递减），我们可以利用这个性质来进行二分查找。

主要思路：

  1. 线性查找：最直观的方法是遍历数组，找到满足 arr[i] > arr[i+1] 的第一个位置，时间复杂度为 O(n)
  2. 二分查找（推荐）：利用山脉数组的特性，通过比较中点与其右邻居的大小关系来缩小搜索范围

二分查找的核心判断：

  • 如果 arr[mid] < arr[mid + 1]，说明峰值在右半部分，更新 left = mid + 1
  • 如果 arr[mid] > arr[mid + 1]，说明峰值在左半部分或就是当前位置，更新 right = mid

这样可以将时间复杂度优化到 O(log n)，满足题目要求。

由于题目保证是山脉数组，峰值一定存在且唯一，所以二分查找一定能找到正确答案。

代码实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = 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) // 2
            
            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                right = mid
        
        return left

public 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;
    }
}

var peakIndexInMountainArray = function(arr) {
    let left = 0, right = arr.length - 1;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        
        if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型二分查找线性查找
时间复杂度O(log n)O(n)
空间复杂度O(1)O(1)

相关题目