[leetcode 852] 山脉数组的峰顶索引
[leetcode 852] 山脉数组的峰顶索引

Problem:

我们把符合下列属性的数组 A 称作山脉:

  • A.length >= 3
  • 存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

给定一个确定为山脉的数组,返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]i 的值。

示例 1:

输入:[0,1,0]
输出:1

示例 2:

输入:[0,2,1,0]
输出:1

提示:

  1. 3 <= A.length <= 10000
  2. 0 <= A[i] <= 10^6
  3. A 是如上定义的山脉

Solution:

如果一个数组是山脉数组,所以该数组一定是先上升,然后又下降的,所以找到该数组的最大值的下标即使峰顶,我们可以用普通的循环遍历的方式,时间复杂度为O(N)。

# 1 : 查找最大值

func peakIndexInMountainArray(A []int) int {
    var maxValue int
    var maxIndex int
    
    for index,value := range A {
        if value > maxValue {
            maxIndex = index
        }
    }
    return maxIndex
}

# 2 :查找山峰的拐点(山顶)

func peakIndexInMountainArray(A []int) int {
	var peakIndex int
	length := len(A)

	for i := 1; i < length-1; i++ {
		if A[i] > A[i-1] && A[i] > A[i+1] {
			peakIndex = i
			break
		}
	}
	return peakIndex
}

If You Have Any Question, You Can Contact Me Through liam@blue7wings.com, @Blue7Wings, #Liam_Hsia