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

╰半夏微凉° 2022-10-07 00:54 68阅读 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 条评论，68人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关 ionic4数组的索引

前言所谓数组，是有序的元素序列。用于区分数组中的各个元素的数字编号称为下标。在平常的使用中，我们可以根据下标去获取或者修改数组中的值，那么在ionic中，我们如何使

曾经终败给现在/ 2022年02月05日 02:45/ 0 赞/ 172 阅读

相关二分查找852

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

绝地灬酷狼/ 2022年01月20日 03:47/ 0 赞/ 85 阅读

相关元胞数组的索引

元胞数组的索引 1. Cell Index 2. Content Index -------------------- >>A = [1 2 3;

╰+攻爆jí腚メ/ 2021年11月18日 00:28/ 0 赞/ 249 阅读