问题- leetcode 852 为什么我的代码超出时间限制

Question

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int s=0;
        int e = arr.size() - 1;

        int mid = s+ (e-s)/2;

        while(s<=e){
            if(arr[mid-1]< arr[mid] && arr[mid]> arr[mid+1]){
                return mid;
            }  
           else if(arr[mid]< arr[mid+1]){
                s = mid +1;
            }
           else{
                e= mid-1;
           }
     
        }
        return -1;
    }
};

我刚刚解决了这个问题，它可以在所有测试用例上运行，但在提交时，结果是超时。 请帮我找出这段代码有什么问题。

Answer 1

mid

应在

while

循环内声明，以便在每次迭代时获取当前间隔的中点。请注意，从 C++ 20 开始，您可以使用

std::midpoint

（而不是

s+ (e-s)/2

）来避免溢出问题。

为了避免访问越界索引，您应该从索引

1

到

arr.size() - 2

进行二分搜索，因为峰值索引永远不可能是数组端点之一。

int s = 1, e = arr.size() - 2;
while (s <= e){
    int mid = std::midpoint(s, e);
    // the rest of your code stays the same
}