运行时错误：将无符号偏移量添加到 0x6030000000d0 溢出到 0x6030000000cc (stl_vector.h)

Question

问题名称：山脉阵列中的峰值索引

该问题需要找到山数组中峰元素的索引。峰值元素定义为大于其邻居的元素。阵列保证有山形图案。

这样：

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 上出现此错误。

Answer 1

在访问

mid

之前，您永远不会检查

0

是否是

arr[mid-1]

，并且在访问

mid

之前，您永远不会检查

arr.size() - 1

是否是

arr[mid+1]

。这两种失败都会导致访问越界。

在访问之前添加检查应使其按照预期设计工作。

int peakIndexInMountainArray(vector<int>& arr) {
    int left = 0, right = arr.size();
    int mid;
    while (left < right) {
        mid = (left + right) / 2;

        bool low = (mid == 0) || (arr[mid] > arr[mid - 1]);
//                 ^^^^^^^^^^
        bool high = (mid == (arr.size() - 1)) || (arr[mid] > arr[mid + 1]);
//                  ^^^^^^^^^^^^^^^^^^^^^^^^^
        if (low && high) {
            return mid;
        } else if (low) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return -1;
}