0852-山脉数组的峰顶索引

Raphael Liu Lv10

符合下列属性的数组 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

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1:

**输入:** arr = [0,1,0]
**输出:** 1

示例 2:

**输入:** arr = [0,2,1,0]
**输出:** 1

示例 3:

**输入:** arr = [0,10,5,2]
**输出:** 1

提示:

  • 3 <= arr.length <= 105
  • 0 <= arr[i] <= 106
  • 题目数据保证 arr 是一个山脉数组

前言

虽然题目描述中说明了「我们可以返回任何满足条件的下标 i」,但由于条件为:

\textit{arr}0 < \textit{arr}_1 < \cdots \textit{arr}_{i-1} < \textit{arr}_i > \textit{arr}{i+1} > \cdots > \textit{arr}_{n-1}

其中 n 是数组 arr 的长度,这说明 arr}_i 是数组中的最大值,并且是唯一的最大值。

因此,我们需要找出的下标 i 一定是唯一的。

方法一:枚举

思路与算法

我们可以对数组 arr 进行一次遍历。

当我们遍历到下标 i 时,如果有 arr}{i-1} < \textit{arr}_i > \textit{arr}{i+1,那么 i 就是我们需要找出的下标。

更简单地,我们只需要让 i 满足 arr}i > \textit{arr}{i+1 即可。在遍历的过程中,我们最先遍历到的满足 arr}i > \textit{arr}{i+1 的下标 i 一定也满足 arr}_{i-1} < \textit{arr}_i。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
int ans = -1;
for (int i = 1; i < n - 1; ++i) {
if (arr[i] > arr[i + 1]) {
ans = i;
break;
}
}
return ans;
}
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int ans = -1;
for (int i = 1; i < n - 1; ++i) {
if (arr[i] > arr[i + 1]) {
ans = i;
break;
}
}
return ans;
}
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int PeakIndexInMountainArray(int[] arr) {
int n = arr.Length;
int ans = -1;
for (int i = 1; i < n - 1; ++i) {
if (arr[i] > arr[i + 1]) {
ans = i;
break;
}
}
return ans;
}
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
n = len(arr)
ans = -1

for i in range(1, n - 1):
if arr[i] > arr[i + 1]:
ans = i
break

return ans
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
var peakIndexInMountainArray = function(arr) {
const n = arr.length;
let ans = -1;

for (let i = 1; i < n - 1; ++i) {
if (arr[i] > arr[i + 1]) {
ans = i;
break;
}
}
return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
func peakIndexInMountainArray(arr []int) int {
for i := 1; ; i++ {
if arr[i] > arr[i+1] {
return i
}
}
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
int peakIndexInMountainArray(int* arr, int arrSize) {
int n = arrSize;
int ans = -1;
for (int i = 1; i < n - 1; ++i) {
if (arr[i] > arr[i + 1]) {
ans = i;
break;
}
}
return ans;
}

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组 arr 的长度。我们最多需要对数组 arr 进行一次遍历。

  • 空间复杂度:O(1)。

方法二:二分查找

思路与算法

记满足题目要求的下标 i 为 i_\textit{ans。我们可以发现:

  • 当 i < i_\textit{ans 时,arr}i < \textit{arr}{i+1 恒成立;

  • 当 i \geq i_\textit{ans 时,arr}i > \textit{arr}{i+1 恒成立。

这与方法一的遍历过程也是一致的,因此 i_\textit{ans 即为「最小的满足 arr}i > \textit{arr}{i+1 的下标 i」,我们可以用二分查找的方法来找出 i_\textit{ans。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
int left = 1, right = n - 2, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > arr[mid + 1]) {
ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
return ans;
}
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int left = 1, right = n - 2, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > arr[mid + 1]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int PeakIndexInMountainArray(int[] arr) {
int n = arr.Length;
int left = 1, right = n - 2, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > arr[mid + 1]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
n = len(arr)
left, right, ans = 1, n - 2, 0

while left <= right:
mid = (left + right) // 2
if arr[mid] > arr[mid + 1]:
ans = mid
right = mid - 1
else:
left = mid + 1

return ans
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var peakIndexInMountainArray = function(arr) {
const n = arr.length;
let left = 1, right = n - 2, ans = 0;

while (left <= right) {
const mid = Math.floor((left + right) /2 );
if (arr[mid] > arr[mid + 1]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
};
[sol2-Golang]
1
2
3
func peakIndexInMountainArray(arr []int) int {
return sort.Search(len(arr)-1, func(i int) bool { return arr[i] > arr[i+1] })
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int peakIndexInMountainArray(int* arr, int arrSize) {
int n = arrSize;
int left = 1, right = n - 2, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > arr[mid + 1]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}

复杂度分析

  • 时间复杂度:O(\log n),其中 n 是数组 arr 的长度。我们需要进行二分查找的次数为 O(\log n)。

  • 空间复杂度:O(1)。

 Comments
On this page
0852-山脉数组的峰顶索引