山峰数组的峰顶索引
题目描述
给定一个长度为 n 的山脉数组 arr，其中存在某个索引 i 使得数组严格递增到 i 然后严格递减。请找到这个峰顶索引 i。
算法思路
暴力遍历虽然可行，但效率较低。观察数组特性，它呈现'先增后减'的趋势，这天然适合二分查找。
分析峰顶位置的数据特点：
- 峰顶数据满足：
arr[i] > arr[i-1]且arr[i] > arr[i+1] - 峰顶左侧呈上升趋势：
arr[mid] < arr[mid+1] - 峰顶右侧呈下降趋势：
arr[mid] > arr[mid+1]
我们可以根据 mid 位置的斜率来收缩搜索区间：
- 如果
arr[mid] > arr[mid-1]，说明处于上升阶段或就是峰顶，目标在右侧（含 mid），令left = mid。 - 否则，说明处于下降阶段，目标在左侧，令
right = 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;
if (arr[mid] > arr[mid - 1]) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
};
寻找峰值
题目描述
给定一个整数数组 nums，找到任意一个峰值元素并返回其索引。假设 nums[-1] = nums[n] = -∞。
算法思路
这道题不需要找特定的'山峰'，只要找到一个比邻居大的点即可。核心在于判断'二段性'。
任取一个点 i，与下一个点 i+1 比较：
- 若
arr[i] > arr[i+1]，说明此处正在下降。由于最左侧边界可视作负无穷，那么左侧区域一定存在一个峰值。 - 若
arr[i] < arr[i+1]，说明此处正在上升。由于最右侧边界可视作负无穷，那么右侧区域一定存在一个峰值。
