[数据结构与算法]剑指 Offer II 069. 山峰数组的顶部

题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/B1IidL

符合下列属性的数组 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)) 的解决方案吗？

解法

• 方法1：使用python自带函数找到max及index

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        return arr.index(max(arr))

• 方法2：循环遍历，判别条件即可, 第一个满足 arr[i] > arr[i+1]的下标

• python

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        n = len(arr)
        for i in range(n):
            if arr[i] > arr[i+1]:
                return i

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

• 方法3： 看到复杂度O(logn) 表示应该用二分法，这题大致满足二分法的条件，左右是顺序的。
  • 峰顶的左边满足从小到大
  • 峰顶的右边满足从大到小
  • 如果中间值比左边值大，表明位于峰顶的左边，改变left
  • 如果中间值比右边大，表明位于峰顶的右边，改变right
• python

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        n = len(arr)
        left = 0
        right = n-1
        while left <= right:
            mid = left + (right-left) // 2
            if arr[mid] > arr[mid+1]:
                ans = mid  # 表明mid是在上升点，暂时设置为顶点
                right = mid - 1
            else:
                left = mid + 1
        return ans
        

• c++

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

复杂度分析

• 时间复杂度：O(n) O(logn)

• 空间复杂度：O(1)