https://leetcode.com/problems/peak-index-in-a-mountain-array/
给定一个 mountain 数组（满足A.length >= 3，There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]），求其最大值
此题与https://leetcode.com/problems/find-peak-element类似，解答参考162. Find Peak Element
简单来说，就是我们希望从 lo-1 到 lo 是一种上升趋势，而从 hi 到 hi + 1 是一种下降趋势，汇合起来就是峰值
class Solution {
public:
int peakIndexInMountainArray(vector<int>& A) {
int lo = 0, hi =A.size()-1;
while(lo < hi)
{
int mi = (lo + hi)>>1;
if(A[mi]<A[mi+1])
lo = mi+1;
else
hi = mi;
}
return lo;
}
};
网友评论