题目形容
这是 LeetCode 上的 852. 山脉数组的峰顶索引 ，难度为 简略。
Tag :「二分」、「三分」
合乎下列属性的数组 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 = [0,2,1,0]
输入：1示例 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})$ 的解决方案吗？
二分
平常咱们应用「二分」进行查值，须要确保序列自身满足「二段性」：入选定一个端点（基准值）后，联合「一段满足 & 另一段不满足」的个性来实现“折半”的查找成果。
但本题求的是峰顶索引值，如果咱们选定数组头部或者尾部元素，其实无奈依据大小关系“间接”将数组分成两段。
但能够利用题目发现如下性质：因为 arr 数值各不相同，因而峰顶元素左侧必然满足严格枯燥递增，峰顶元素右侧必然不满足。
因而 以峰顶元素为宰割点的 arr 数组，依据与 前一元素 / 后一元素 的大小关系，具备二段性：
- 峰顶元素左侧满足 $arr[i-1] < arr[i]$ 性质，右侧不满足
- 峰顶元素右侧满足 $arr[i] > arr[i+1]$ 性质，左侧不满足
因而咱们能够抉择任意条件，写出若干「二分」版本。
代码：
class Solution {// 依据 arr[i-1] < arr[i] 在 [1,n-1] 范畴内找值
// 峰顶元素为符合条件的最靠近核心的元素
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int l = 1, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (arr[mid - 1] < arr[mid]) l = mid;
else r = mid - 1;
}
return r;
}
}class Solution {// 依据 arr[i] > arr[i+1] 在 [0,n-2] 范畴内找值
// 峰顶元素为符合条件的最靠近核心的元素值
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int l = 0, r = n - 2;
while (l < r) {
int mid = l + r >> 1;
if (arr[mid] > arr[mid + 1]) r = mid;
else l = mid + 1;
}
return r;
}
}class Solution {// 依据 arr[i-1] > arr[i] 在 [1,n-1] 范畴内找值
// 峰顶元素为符合条件的最靠近核心的元素的前一个值
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int l = 1, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (arr[mid - 1] > arr[mid]) r = mid;
else l = mid + 1;
}
return r - 1;
}
}class Solution {// 依据 arr[i] < arr[i+1] 在 [0,n-2] 范畴内找值
// 峰顶元素为符合条件的最靠近核心的元素的下一个值
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int l = 0, r = n - 2;
while (l < r) {
int mid = l + r + 1 >> 1;
if (arr[mid] < arr[mid + 1]) l = mid;
else r = mid - 1;
}
return r + 1;
}
}- 工夫复杂度：$O(\log{n})$
- 空间复杂度：$O(1)$
三分
事实上，咱们还能够利用「三分」来解决这个问题。
顾名思义，「三分」就是应用两个端点将区间分成三份，而后通过每次否决三分之一的区间来迫近目标值。
具体的，因为峰顶元素为全局最大值，因而咱们能够每次将以后区间分为 $[l, m1]$、$[m1, m2]$ 和 $[m2, r]$ 三段，如果满足 $arr[m1] > arr[m2]$，阐明峰顶元素不可能存在与 $[m2, r]$ 中，让 $r = m2 – 1$ 即可。另外一个区间剖析同理。
代码：
class Solution {public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int l = 0, r = n - 1;
while (l < r) {int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (arr[m1] > arr[m2]) r = m2 - 1;
else l = m1 + 1;
}
return r;
}
}- 工夫复杂度：$O(\log_3{n})$
- 空间复杂度：$O(1)$
二分 & 三分 & k 分？
必须阐明一点，「二分」和「三分」在渐进复杂度上都是一样的，都能够通过换底公式转化为可疏忽的常数，因而两者的复杂度都是 $O(\log{n})$。
而抉择「二分」还是「三分」取决于要解决的是什么问题：
- 二分通常用来解决枯燥函数的找 $target$ 问题，但进一步深刻咱们发现只须要满足「二段性」就能应用「二分」来找宰割点；
- 三分则是解决单峰函数极值问题。
因而个别咱们将「通过比拟两个端点，每次否决 1/3 区间 来解决单峰最值问题」的做法称为「三分」；而不是简略依据单次循环内将区间分为多少份来断定是否为「三分」。
顺手写了一段反例代码：
class Solution {public int peakIndexInMountainArray(int[] arr) {
int left = 0, right = arr.length - 1;
while(left < right) {int m1 = left + (right - left) / 3;
int m2 = right - (right - left + 2) / 3;
if (arr[m1] > arr[m1 + 1]) {right = m1;} else if (arr[m2] < arr[m2 + 1]) {left = m2 + 1;} else {left = m1; right = m2;}
}
return left;
}
}这并不是「三分」做法，最多称为「变形二分」。实质还是利用「二段性」来做宰割的，只不过同时 check 了两个端点而已。
如果这算「三分」的话，那么我能在一次循环外面划分 $k – 1$ 个端点来实现 $k$ 分？
显然这是没有意义的，因为依照这种思路写进去的所谓的「四分」、「五分」、「k 分」是须要减少等同数量的分支判断的。这时候单次 while 决策就不能算作 $O(1)$ 了，而是须要在 $O(k)$ 的复杂度内决定在哪个分支，就跟上述代码有三个分支进行判断一样。
因而，这种写法只能算作是「变形二分」。
综上，只有「二分」和「三分」的概念，不存在所谓的 $k$ 分。 同时题解中的「三分」局部提供的做法就是规范的「三分」做法。
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.852 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布