LCR 069-山脉数组的峰顶索引

符合下列属性的数组 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 ，返回任何满足 `arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i

• 1] > … > arr[arr.length - 1]的下标i` ，即山峰顶部。

示例 1：

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

示例 2：

**输入：** arr = [1,3,5,4,2]
**输出：2**

示例 3：

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

示例 4：

**输入：** arr = [3,4,5,1]
**输出：** 2

示例 5：

**输入：** arr = [24,69,100,99,79,78,67,36,26,19]
**输出：** 2

提示：

• 3 <= arr.length <= 104
• 0 <= arr[i] <= 106
• 题目数据保证 arr 是一个山脉数组

进阶： 很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？

注意：本题与主站 852 题相同：<https://leetcode-cn.com/problems/peak-index-in-a-mountain-
array/>

前言

虽然题目描述中说明了「我们可以返回任何满足条件的下标 i」，但由于条件为：

\textit{arr}0 < \textit{arr}_1 < \cdots \textit{arr}_{i-1} < \textit{arr}_i > \textit{arr}{i+1} > \cdots > \textit{arr}_{n-1}

其中 n 是数组 arr 的长度，这说明 arr}_i 是数组中的最大值，并且是唯一的最大值。

因此，我们需要找出的下标 i 一定是唯一的。

方法一：枚举

思路与算法

我们可以对数组 arr 进行一次遍历。

当我们遍历到下标 i 时，如果有 arr}{i-1} < \textit{arr}_i > \textit{arr}{i+1，那么 i 就是我们需要找出的下标。

更简单地，我们只需要让 i 满足 arr}i > \textit{arr}{i+1 即可。在遍历的过程中，我们最先遍历到的满足 arr}i > \textit{arr}{i+1 的下标 i 一定也满足 arr}_{i-1} < \textit{arr}_i。

代码

[sol1-C++]

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        int ans = -1;
        for (int i = 1; i < n - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                ans = i;
                break;
            }
        }
        return ans;
    }
};

[sol1-Java]

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int ans = -1;
        for (int i = 1; i < n - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                ans = i;
                break;
            }
        }
        return ans;
    }
}

[sol1-C#]

public class Solution {
    public int PeakIndexInMountainArray(int[] arr) {
        int n = arr.Length;
        int ans = -1;
        for (int i = 1; i < n - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                ans = i;
                break;
            }
        }
        return ans;
    }
}

[sol1-Python3]

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        n = len(arr)
        ans = -1

        for i in range(1, n - 1):
            if arr[i] > arr[i + 1]:
                ans = i
                break
        
        return ans

[sol1-JavaScript]

var peakIndexInMountainArray = function(arr) {
    const n = arr.length;
    let ans = -1;

    for (let i = 1; i < n - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            ans = i;
            break;
        }
    }
    return ans;
};

[sol1-Golang]

func peakIndexInMountainArray(arr []int) int {
    for i := 1; ; i++ {
        if arr[i] > arr[i+1] {
            return i
        }
    }
}

[sol1-C]

int peakIndexInMountainArray(int* arr, int arrSize) {
    int n = arrSize;
    int ans = -1;
    for (int i = 1; i < n - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            ans = i;
            break;
        }
    }
    return ans;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 arr 的长度。我们最多需要对数组 arr 进行一次遍历。

• 空间复杂度：O(1)。

方法二：二分查找

思路与算法

记满足题目要求的下标 i 为 i_\textit{ans。我们可以发现：

• 当 i < i_\textit{ans 时，arr}i < \textit{arr}{i+1 恒成立；

• 当 i \geq i_\textit{ans 时，arr}i > \textit{arr}{i+1 恒成立。

这与方法一的遍历过程也是一致的，因此 i_\textit{ans 即为「最小的满足 arr}i > \textit{arr}{i+1 的下标 i」，我们可以用二分查找的方法来找出 i_\textit{ans。

代码

[sol2-C++]

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        int left = 1, right = n - 2, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > arr[mid + 1]) {
                ans = mid;
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return ans;
    }
};

[sol2-Java]

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int left = 1, right = n - 2, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > arr[mid + 1]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

[sol2-C#]

public class Solution {
    public int PeakIndexInMountainArray(int[] arr) {
        int n = arr.Length;
        int left = 1, right = n - 2, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > arr[mid + 1]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

[sol2-Python3]

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        n = len(arr)
        left, right, ans = 1, n - 2, 0

        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > arr[mid + 1]:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return ans

[sol2-JavaScript]

var peakIndexInMountainArray = function(arr) {
    const n = arr.length;
    let left = 1, right = n - 2, ans = 0;

    while (left <= right) {
        const mid = Math.floor((left + right) /2 );
        if (arr[mid] > arr[mid + 1]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
};

[sol2-Golang]

func peakIndexInMountainArray(arr []int) int {
    return sort.Search(len(arr)-1, func(i int) bool { return arr[i] > arr[i+1] })
}

[sol2-C]

int peakIndexInMountainArray(int* arr, int arrSize) {
    int n = arrSize;
    int left = 1, right = n - 2, ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] > arr[mid + 1]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

复杂度分析

• 时间复杂度：O(\log n)，其中 n 是数组 arr 的长度。我们需要进行二分查找的次数为 O(\log n)。

• 空间复杂度：O(1)。