大家好，我是小卡皮巴拉
文章目录
目录
力扣题目：山脉数组的峰顶索引
题目描述
解题思路
问题理解
算法选择
具体思路
解题要点
完整代码（C++）
兄弟们共勉 ！！！
每篇前言
博客主页：小卡皮巴拉
咱的口号：🌹小比特，大梦想🌹
作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。
力扣题目：山脉数组的峰顶索引
原题链接：852. 山脉数组的峰顶索引 - 力扣（LeetCode）
题目描述
给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
输入：arr = [0,1,0] 输出：1
示例 2：
输入：arr = [0,2,1,0] 输出：1
示例 3：
输入：arr = [0,10,5,2] 输出：1
解题思路
问题理解
本题给定一个长度为 n 的整数数组 arr，该数组呈现山脉形状，即先递增到一个峰值元素，然后递减。要求返回这个峰值元素的下标，并且要求设计并实现时间复杂度为 O(log(n)) 的解决方案。
算法选择
采用二分查找算法来解决此问题。因为山脉数组的特性，通过二分查找可以在对数时间复杂度内找到峰值元素。
具体思路
-
初始化左右指针：
-
定义两个指针
left和right，由于数组两端的元素（arr[0]和arr[arr.size() - 1]）不可能是峰值元素（因为它们不满足先递增后递减的条件），所以left初始化为1，right初始化为arr.size() - 2。
-
-
二分查找过程：
-
使用
while循环，当left < right时，执行以下操作：-
计算中间位置
mid，为了保证在left和right相差1时mid能取到right的值（因为我们希望在这种情况下能够继续判断mid及其相邻元素的大小关系），使用mid = left + (right - left + 1) / 2计算。 -
比较
arr[mid]和arr[mid - 1]的大小：-
如果
arr[mid] < arr[mid - 1]，说明mid位置的元素处于递减阶段，那么峰值元素在mid的左侧，将right更新为mid - 1。 -
如果
arr[mid] >= arr[mid - 1]，说明mid位置的元素处于递增阶段或者就是峰值元素，那么峰值元素在mid或其右侧，将left更新为mid。
-
-
-
-
返回结果：
-
当
left和right相遇时，循环结束，此时left指向的位置就是峰值元素的下标，返回left。
-
解题要点
-
指针初始化：正确初始化
left和right，排除数组两端元素不可能是峰值元素的情况。 -
中间位置计算：使用
mid = left + (right - left + 1) / 2计算中间位置，确保在各种情况下都能正确计算并覆盖到所有可能的位置。 -
比较判断：通过比较
arr[mid]和arr[mid - 1]的大小关系，准确地缩小峰值元素所在的范围，保证最终能找到峰值元素的下标。
完整代码（C++）
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size() - 2; // 初始化左右指针，排除数组两端元素，因为它们不可能是峰值元素while (left < right) // 当左指针小于右指针时，继续二分查找{int mid = left + (right - left + 1) / 2; // 计算中间位置，确保在 left 和 right 相差 1 时 mid 能取到 right 的值if (arr[mid] < arr[mid - 1]) // 如果中间元素小于其前一个元素，说明处于递减阶段right = mid - 1; // 峰值元素在 mid 的左侧，更新右指针elseleft = mid; // 如果中间元素大于等于其前一个元素，说明处于递增阶段或就是峰值元素，更新左指针}return left; // 循环结束，left 指向峰值元素的下标，返回 left}
};兄弟们共勉 ！！！
码字不易，求个三连
抱拳了兄弟们！
