【Day50】852. 山脉数组的峰顶索引

852. 山脉数组的峰顶索引

符合下列属性的数组 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 = [0,2,1,0]
输出:1

示例 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 是一个山脉数组

题解:

二分法

class Solution {
public:
    int peakIndexInMountainArray(vector& arr) {
            //根据 arr[mid-1]和arr[mid]对比
        //所以搜索范围是 [1,arr.length -1]
        int left = 1;
        int right = arr.size() - 1;

        while(left < right){
            //如果check 函数调整的是left,则+1. 否则有可能陷入死循环
            int mid = left + right + 1 >> 1;
            if(arr[mid-1] < arr[mid])
            left = mid;
            else
            right = mid -1;
        }
        return right;
    }
};

   转载规则


《【Day50】852. 山脉数组的峰顶索引》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day51】877. 石子游戏 【Day51】877. 石子游戏
877. 石子游戏亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。 亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的
2021-06-16
下一篇 
【Day49】374. 猜数字大小 【Day49】374. 猜数字大小
374. 猜数字大小猜数字游戏的规则如下: 每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 int
2021-06-14
  目录