加载中...
剑指 Offer II 069-山峰数组的顶部
发表于:2021-12-03 | 分类: 简单
字数统计: 2.6k | 阅读时长: 10分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/B1IidL

中文题目

符合下列属性的数组 arr 称为 山峰数组山脉数组)

  • arr.length >= 3
  • 存在 i0 < 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)) 的解决方案吗?

 

注意:本题与主站 852 题相同:https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/

通过代码

高赞题解

二分

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

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

但可以利用题目发现如下性质:由于 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; int m2 = r - (r - l) / 3; if (arr[m1] > arr[m2]) r = m2 - 1; else l = m1 + 1; } return r; } }
  • 时间复杂度:$O(\log{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$ 分。 同时题解中的「三分」部分提供的做法就是标准的「三分」做法。


进阶

更进一步的,如果存在多个峰值,返回任意一个的话,是否还可以二分?为什么?

(原题)162. 寻找峰值 : (题解)关于能够「二分」的两点证明


其他「二分」内容

题目简单?考虑加餐一道 01 背包变形题

或是考虑加练如下「二分」题目 🍭🍭

题目 题解 难度 推荐指数
4. 寻找两个正序数组的中位数 LeetCode 题解链接 困难 🤩🤩🤩🤩
29. 两数相除 LeetCode 题解链接 中等 🤩🤩🤩
33. 搜索旋转排序数组 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
34. 在排序数组中查找元素的第一个和最后一个位置 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
35. 搜索插入位置 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
74. 搜索二维矩阵 LeetCode 题解链接 中等 🤩🤩🤩🤩
81. 搜索旋转排序数组 II LeetCode 题解链接 中等 🤩🤩🤩🤩
153. 寻找旋转排序数组中的最小值 LeetCode 题解链接 中等 🤩🤩🤩
154. 寻找旋转排序数组中的最小值 II LeetCode 题解链接 困难 🤩🤩🤩
162. 寻找峰值 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
220. 存在重复元素 III LeetCode 题解链接 中等 🤩🤩🤩
274. H 指数 LeetCode 题解链接 中等 🤩🤩🤩
275. H 指数 II LeetCode 题解链接 中等 🤩🤩🤩
278. 第一个错误的版本 LeetCode 题解链接 简单 🤩🤩🤩🤩
352. 将数据流变为多个不相交区间 LeetCode 题解链接 困难 🤩🤩🤩🤩
354. 俄罗斯套娃信封问题 LeetCode 题解链接 困难 🤩🤩🤩
363. 矩形区域不超过 K 的最大数值和 LeetCode 题解链接 困难 🤩🤩🤩
374. 猜数字大小 LeetCode 题解链接 简单 🤩🤩🤩
441. 排列硬币 LeetCode 题解链接 简单 🤩🤩🤩
528. 按权重随机选择 LeetCode 题解链接 中等 🤩🤩🤩🤩
611. 有效三角形的个数 LeetCode 题解链接 中等 🤩🤩🤩🤩
704. 二分查找 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
778. 水位上升的泳池中游泳 LeetCode 题解链接 困难 🤩🤩🤩
852. 山脉数组的峰顶索引 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
981. 基于时间的键值存储 LeetCode 题解链接 中等 🤩🤩🤩🤩
1004. 最大连续1的个数 III LeetCode 题解链接 中等 🤩🤩🤩
1011. 在 D 天内送达包裹的能力 LeetCode 题解链接 中等 🤩🤩🤩🤩
1208. 尽可能使字符串相等 LeetCode 题解链接 中等 🤩🤩🤩
1337. 矩阵中战斗力最弱的 K 行 LeetCode 题解链接 简单 🤩🤩🤩
1438. 绝对差不超过限制的最长连续子数组 LeetCode 题解链接 中等 🤩🤩🤩
1482. 制作 m 束花所需的最少天数 LeetCode 题解链接 中等 🤩🤩🤩
1707. 与数组中元素的最大异或值 LeetCode 题解链接 困难 🤩🤩🤩
1713. 得到子序列的最少操作次数 LeetCode 题解链接 困难 🤩🤩🤩
1751. 最多可以参加的会议数目 II LeetCode 题解链接 困难 🤩🤩🤩
1818. 绝对差值和 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
1838. 最高频元素的频数 LeetCode 题解链接 中等 🤩🤩🤩
1894. 找到需要补充粉笔的学生编号 LeetCode 题解链接 中等 🤩🤩🤩🤩
剑指 Offer 53 - I. 在排序数组中查找数字 I LeetCode 题解链接 简单 🤩🤩🤩🤩🤩

注:以上目录整理来自 wiki,任何形式的转载引用请保留出处。


最后

如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我(公主号后台回复「送书」即可参与长期看题解学算法送实体书活动)或 加入「组队打卡」小群 ,提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南,欢迎 star 哦 ~

统计信息

通过次数 提交次数 AC比率
37763 52325 72.2%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
上一篇:
剑指 Offer II 068-查找插入位置
下一篇:
剑指 Offer II 070-排序数组中只出现一次的数字
本文目录
本文目录