021 山脉数组的峰顶索引
题目描述：
C++算法
二分查找算法：山脉数组的峰顶索引与寻找峰值
二分查找算法应用于山脉数组峰顶索引与寻找峰值问题。通过暴力遍历与二分查找思路对比，利用数组上升下降趋势构建二段性，确定搜索区间。核心在于根据 mid 与相邻元素关系调整左右边界，将时间复杂度从 O(n) 优化至 O(logn)。提供 C++ 代码实现及详细逻辑推导。
二分查找算法应用于山脉数组峰顶索引与寻找峰值问题。通过暴力遍历与二分查找思路对比，利用数组上升下降趋势构建二段性，确定搜索区间。核心在于根据 mid 与相邻元素关系调整左右边界，将时间复杂度从 O(n) 优化至 O(logn)。提供 C++ 代码实现及详细逻辑推导。
题目描述：
峰顶的特点：比两侧的元素都要大。 因此，我们可以遍历数组内的每一个元素，找到某一个元素比两边的元素大即可。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
// 遍历数组内每一个元素，直到找到峰顶
for (int i = 1; i < n - 1; i++) {
// 峰顶满足的条件
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
return i;
}
// 为了处理 oj 需要控制所有路径都有返回值
return -1;
}
};
时间复杂度：O(n)，空间复杂度：O(1)。
1、分析峰顶位置的数据特点，以及山峰两旁的数据的特点：
（1）峰顶数据特点：arr[i] > arr[i - 1] && arr[i] > arr[i + 1]；
（2）峰顶左边的数据特点：arr[i] > arr[i - 1] && arr[i] < arr[i + 1]，也就是呈现上升趋势；
（3）峰顶右边数据的特点：arr[i] < arr[i - 1] && arr[i] > arr[i + 1]，也就是呈现下降趋势。
2、因此，根据 mid 位置的信息，我们可以分为下面三种情况：
（1）如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索；
（2）如果 mid 位置呈现下降趋势，说明我们接下来要在 [left, mid - 1] 区间搜索；
（3）如果 mid 位置就是山峰，直接返回结果。
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;
if (arr[mid] > arr[mid - 1])
left = mid;
else
right = mid - 1;
}
return left;
}
};
时间复杂度：O(logn)，空间复杂度：O(1)。
题目描述：
寻找二段性——
任取一个点 i，与下一个点 i + 1，会有如下两种情况：
（1）arr[i] > arr[i + 1]：此时【左侧区域】一定会存在山峰（因为最左侧是负无穷），那么我们可以去左侧去寻找结果；
（2）arr[i] < arr[i + 1]：此时【右侧区域】一定会存在山峰（因为最右侧是负无穷），那么我们可以去右侧去寻找结果。
当我们找到【二段性】的时候，就可以尝试用【二分查找】算法来解决问题。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1])
left = mid + 1;
else
right = mid;
}
return left;
}
};
时间复杂度：O(logn)，空间复杂度：O(1)。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online