• 小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。
• 本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

leetcode-剑指offer069-山峰数组的顶部

[博客链接]

菜🐔的学习之路

掘金首页

[题目链接]

题目链接

[github地址]

github地址

[题目描述]

符合下列属性的数组 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>n-1直接扫描即可
• 代码我就不写了
• 时间复杂度O(n)
• 空间复杂度O(1)

思路二：二分查找

• 之前很多次二分的题解中已经说明可以不可以二分二分不是只是判断是否又须而是是否具备两段性
• 本题就有很明显的两段性特征
  • 峰顶元素左侧具有递增性质
  • 峰顶元素右侧具有递减性质
• 所以我们可以从这方面入手作为二分判断的依据
• 因为一定是山峰数组所以一定存在峰顶元素
• 因此我们不再需要考虑边界为峰顶元素的可能性
• 二分的边界也只需要考虑1 -> n-1 即可
• 同时由于不存在相同元素，边界移动可以直接+-1

class Solution {
        public int peakIndexInMountainArray(int[] arr) {
            int l = 0, n = arr.length, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (mid == 0) {
                    l = mid + 1;
                    continue;
                }
                if (mid == n - 1) {
                    r = mid - 1;
                    continue;
                }
                if (arr[mid] > arr[mid + 1]) {
                    if (arr[mid] > arr[mid - 1]) {
                        return mid;
                    }
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return l;
        }
    }
复制代码

• 时间复杂度O(lgn)
• 空间复杂度O(1)
• ps: 我们再次强调一下是否可以判断二分的标志是是否满足二段性
• 不要简简单单根据有序性判断是否可以二分
• 同时当做题的时候遇到lgn级别的时间复杂度要求第一时间就要想到二分或者分治
• 大家可以做做二分专题找找手感
• 至于二分的模版大家可以参考三叶的模版去背
• 也可以自己手动模拟几个边界case，加深理解