LeetCode 劍指 Offer II 069. 山峰數(shù)組的頂部

@TOC

題目描述

?符合下列屬性的數(shù)組 arr 稱為 山峰數(shù)組（山脈數(shù)組） ：

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] 給定由整數(shù)組成的山峰數(shù)組 arr ，返回任何滿足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下標 i ，即山峰頂部

示例：

輸入：arr = [0,1,0]
輸出：1

提示：

3 <= arr.length <= 104
0 <= arr[i] <= 106
題目數(shù)據(jù)保證 arr 是一個山脈數(shù)組

一、解題關(guān)鍵詞

題目數(shù)據(jù)保證 arr 是一個山脈數(shù)組
頂峰，也就是部分有序

二、解題報告

1.思路分析

1. 部分有序 一定要使用二分思想（left + right + mid）

2. 需要找到最大值

3. 左節(jié)點 右節(jié)點 不斷++ --；

2.時間復(fù)雜度

3.代碼示例

暴力:

class Solution {
? ?public int peakIndexInMountainArray(int[] arr) {
? ? ? ?int ans = 0;
? ? ? ?for(int i = 1;i < arr.length - 1;i++){
? ? ? ? ? ?if(arr[i] > arr[i - 1] && arr[i] > arr[i + 1]){
? ? ? ? ? ? ? ?ans = i;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return ans;
? ?}
}

二分：

class Solution {
? ?public int peakIndexInMountainArray(int[] arr) {
? ? ? ?int len = arr.length;
? ? ? ?int left = 1,right = len - 2;

? ? ? ?while(left <= right){
? ? ? ? ? ?int mid = left +(right - left)/ 2;
? ? ? ? ? ?if(arr[mid - 1] < arr[mid]){
? ? ? ? ? ? ? ?left = mid + 1;
? ? ? ? ? ?}else{
? ? ? ? ? ? ? ?right = mid - 1;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return right;
? ?}
}

4.知識點

5 思考

1. 如果一開始就是降序，怎么辦？

2. 為什么要想到二分，折半且有序 就要二分