符合下列属性的数组 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)) 的解决方案吗?
注意:本题与主站 852 题相同
1、遍历;时间复杂度O(n),空间复杂度O(1)
func peakIndexInMountainArray(arr []int) int {
n := len(arr)
for i := 0; i < n-1; i++ {
if arr[i] > arr[i+1] {
return i
}
}
return 0
}
2、二分查找;时间复杂度O(log(n)),空间复杂度O(1)
func peakIndexInMountainArray(A []int) int {
left, right := 0, len(A)-1
for {
mid := left + (right-left)/2
if A[mid] > A[mid+1] && A[mid] > A[mid-1] {
return mid
}
if A[mid] > A[mid-1] {
left = mid + 1
} else {
right = mid
}
}
}
3、内置函数;时间复杂度O(log(n)),空间复杂度O(1)
func peakIndexInMountainArray(arr []int) int {
n := len(arr)
return sort.Search(n-1, func(i int) bool {
return arr[i] > arr[i+1]
})
}
Easy题目,题目同leetcode 852.山脉数组的峰顶索引
页面更新:2024-02-19
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号