852. 山脉数组的峰顶索引

Posted on | In
Words count in article: 371 | Reading time ≈ 1

题目

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

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

示例2：

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

示例3：

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

示例4：

1
2
输入：arr = [3,4,5,1]
输出：2

示例5：

1
2
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

提示：

  • 3 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^6
  • 题目数据保证 arr 是一个山脉数组

解法

解法一：

遍历，找到index，是的a[index - 1] < a[index] 并且 a[index] > a[index + 1]

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int index = 0;
        int result = 0;
        int end = A.length - 2;
        while (index <= end) {
        	if (A[index] < A[index + 1]) {
        		index++;
        	} else if (A[index] > A[index + 1]) {
        		result = index;
        		break;
        	}
        }
        return result;
    }
}

解法二：

二分查找，每次找到A[i]，确认是否A[i] < A[i + 1]，不是的话，不断缩小上届和下界，找到最大的i为止。

Java

1
2
3
4
5
6
7
8
9
10
11
12
public int peakIndexInMountainArray(int[] A) {
        int lo = 0, hi = A.length - 1;
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (A[mi] < A[mi + 1]) {
                lo = mi + 1;
            } else {
                hi = mi;
            }
        }
        return lo;
    }
0%