Leetcode山峰数组峰值索引求解代码触发运行时错误求助

给定一个符合山峰模式的数组：存在索引i，满足arr[0] < arr[1] < ... < arr[i-1] < arr[i]且arr[i] > arr[i+1] > ... > arr[arr.length-1]，要求找出这个峰值元素的索引i。

以下是我写的简化代码：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            } else if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }  
};

部分测试用例能正常运行，但输入{3, 5, 3, 2, 0}时触发运行时错误：

runtime error: addition of unsigned offset to 0x6030000000d0 overflowed to 0x6030000000cc (stl_vector.h)

本地编译器运行没问题，但提交到Leetcode就报错，求解决办法。

问题原因 #

核心问题是数组越界访问。当mid等于0时，arr[mid-1]就是arr[-1]，属于非法内存访问；同理当mid等于数组最后一个索引时，arr[mid+1]也会越界。

拿测试用例{3,5,3,2,0}来说：初始left=0，right=4，第一次计算mid=2，此时arr[2]=3大于arr[3]=2，进入else分支，right=1。接下来循环中left=0，right=1，mid=0，这时候执行arr[mid-1]也就是arr[-1]，直接触发越界错误。

本地编译器没报错是因为内存布局刚好没触发崩溃，但这种访问本身属于未定义行为，Leetcode的判题环境更严格，直接检测到了越界问题。

修复方案 #

题目明确数组是严格山峰模式，所以峰值不可能在数组首尾（首尾元素只有一个相邻元素，不符合“大于相邻元素”的定义）。我们可以通过调整二分边界或优化判断逻辑来避免越界：

方案1：优化二分逻辑（更简洁） #

利用山峰数组的单调性，不用同时检查左右相邻元素：

• 如果arr[mid] < arr[mid+1]，说明峰值在mid右侧，调整left=mid+1
• 否则峰值在mid或左侧，调整right=mid
• 当left==right时，这个位置就是峰值

修复后的代码：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

方案2：调整初始边界（保留原判断逻辑） #

把left初始化为1，right初始化为arr.size()-2，确保mid始终在[1, arr.size()-2]范围内，避免访问mid-1或mid+1时越界：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            } else if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 题目保证是山峰数组，理论上不会走到这里
        return left;
    }  
};

验证说明 #

以测试用例{3,5,3,2,0}为例，修复后的代码第一次计算mid=2，因为arr[2]=3不小于arr[3]=2，所以right=2；接下来left=0，right=2，mid=1，此时arr[1]=5大于左右相邻元素，直接返回1，正确且无越界。

内容的提问来源于stack exchange，提问作者Nikhil Kumar