[数据结构与算法]剑指 Offer II 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 <= 10^4
0 <= arr[i] <= 10^6
题目数据保证 arr 是一个山脉数组

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

题解

法一：一次遍历

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

        return -1;
    }
};

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

法二：二分查找
代码一：

//本题二分我们使用[l, r)即， 右区间取不到
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int ans;
        int l = 1, r = arr.size() - 1;
        while(l < r)
        {
            int mid = (r - l) / 2 + l;
            if (arr[mid] > arr[mid + 1])
            {
                ans = mid;
                r = mid;
            }
            else 
                l = mid + 1;
        }

        return ans;
    }
};

代码二：

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

        return ans;
    }
};

法三：三分查找

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int l = 1, r = arr.size() - 2;//保证左右边界都可以取到
        while(l < r)
        {
            int mid1 = l + (r - l) / 3;
            int mid2 = r - (r - l) / 3;
            if (arr[mid1] > arr[mid2])
                r = mid2 - 1;
            else
                l = mid1 + 1;
        }
        
        return l;
    }
};

法四：partition_point
参考官方题解评论区下梦璃夜·天星
Tips

参考评论区官方题解

partition_point()的意思是按照指定的条件寻找数组的分割点,从[First, Last)
所以第二个参数为end(arr) - 1而不是end(arr) - 2

第三个参数描述了一个匿名函数 x表示的为数组arr中的元素,*((&x) + 1)拿到
x 之后的元素返回，
返回arr[x+1] > arr[x]的布尔值 这个函数会返回第一个符合条件的迭代器。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        return partition_point(begin(arr) + 1, end(arr) - 1, [](auto&& x){ return *((&x) + 1) > x;}) - begin(arr);
    }
};