852. 山脉数组的峰顶索引【二分 C++】

╰半夏微凉° 2022-10-07 00:54 129阅读 0赞

符合下列属性的数组 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 是一个山脉数组

进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？

class Solution {
    public:
        int peakIndexInMountainArray(vector<int>& arr) {
            int l = 1, r = arr.size()-2, mid;
            while(l<r)
            {
                mid = (l+r)/2;
                if(arr[mid]<arr[mid+1])
                {
                    l = mid+1;
                }
                else
                {
                    if(arr[mid]>arr[mid-1]) return mid;
                    else{
                        r = mid-1;
                    }
                }
            }
            return l;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|二分查找No.4】leetcode 852. 山脉数组的峰顶索引

【算法|二分查找No.4】leetcode 852. 山脉数组的峰顶索引

客官°小女子只卖身不卖艺/ 2024年04月27日 06:56/ 0 赞/ 70 阅读

相关 Leetcode刷题java之852. 山脉数组的峰顶索引

行结果：通过显示详情执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户内存消耗 :42.8 MB, 在所有 Java 提交中击败了...

淡淡的烟草味﹌/ 2024年04月17日 18:21/ 0 赞/ 64 阅读

相关【算法挨揍日记】day11——852. 山脉数组的峰顶索引、162. 寻找峰值

![b73daf6ed95e456ebffd428464edf0f4.png][] 852. 山脉数组的峰顶索引 [852. 山脉数组的峰顶索引][852.] 题目

野性酷女/ 2024年02月27日 04:02/ 0 赞/ 43 阅读

相关 JAVA解决山脉数组的峰顶索引问题

JAVA解决山脉数组的峰顶索引问题 01 题目符合下列属性的数组 `arr` 称为山峰数组（山脉数组）： `arr.length >= 3` 存

女爷i/ 2024年02月05日 18:40/ 0 赞/ 48 阅读

相关 852. 山脉数组的峰顶索引

符合下列属性的数组 `arr` 称为山脉数组： `arr.length >= 3` 存在 `i`（`0 < i < arr.length - 1`）使得：

╰半夏微凉°/ 2023年10月05日 19:49/ 0 赞/ 15 阅读

相关 LeetCode 852. Peak Index in a Mountain Array (山脉数组的峰顶索引)

题目标签：Binary Search 　　题目给了我们一组 int array，让我们找到数组的 peak。　　利用 binary search，如果数字比它后面那个数

待我称王封你为后i/ 2023年08月17日 16:45/ 0 赞/ 96 阅读

相关 C语言重构【852】山脉数组的峰顶索引

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

Myth丶恋晨/ 2022年12月20日 02:06/ 0 赞/ 150 阅读

相关 852. 山脉数组的峰顶索引

2021-06-15 LeetCode每日一题链接：[https://leetcode-cn.com/problems/peak-index-in-a-mountain

柔情只为你懂/ 2022年10月07日 02:59/ 0 赞/ 136 阅读

相关 852. 山脉数组的峰顶索引【二分 C++】

符合下列属性的数组 arr 称为山脉数组： arr.length >= 3 存在 i（0 < i < arr.length - 1）使得： arr\[0\] <

╰半夏微凉°/ 2022年10月07日 00:54/ 0 赞/ 130 阅读

相关 LeetCode852. 山脉数组的峰顶索引

我们把符合下列属性的数组 `A` 称作山脉： `A.length >= 3` 存在 `0 < i < A.length - 1` 使得`A[0] < A[1] <

朴灿烈づ我的快乐病毒、/ 2022年05月17日 00:54/ 0 赞/ 162 阅读