单峰函数极值问题的解决方案 : 三分 & 二分与三分的本质区别

单峰函数极值问题的解决方案 : 三分 & 二分与三分的本质区别

题目描述

这是 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

提示：

二分

往常我们使用「二分」进行查值，需要确保序列本身满足「二段性」：当选定一个端点（基准值）后，结合「一段满足 & 另一段不满足」的特性来实现“折半”的查找效果。

但本题求的是峰顶索引值，如果我们选定数组头部或者尾部元素，其实无法根据大小关系“直接”将数组分成两段。

但可以利用题目发现如下性质：由于 ​​arr​​ 数值各不相同，因此峰顶元素左侧必然满足严格单调递增，峰顶元素右侧必然不满足。

因此 以峰顶元素为分割点的 ​​arr​​ 数组，根据与 前一元素/后一元素 的大小关系，具有二段性：

因此我们可以选择任意条件，写出若干「二分」版本。

代码：

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

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

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

三分

事实上，我们还可以利用「三分」来解决这个问题。

顾名思义，「三分」就是使用两个端点将区间分成三份，然后通过每次否决三分之一的区间来逼近目标值。

代码：

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

二分 & 三分 & k 分 ？

而选择「二分」还是「三分」取决于要解决的是什么问题：

因此一般我们将「通过比较两个端点，每次否决 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

这并不是「三分」做法，最多称为「变形二分」。本质还是利用「二段性」来做分割的，只不过同时 check 了两个端点而已。

因此，这种写法只能算作是「变形二分」。

最后

这是我们「刷穿 LeetCode」系列文章的第 ​​No.852​​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：​​github.com/SharingSour…​​ 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。