c++ - 运行时错误 : addition of unsigned offset to 0x603000000040 overflowed to 0x603000000034 (STL_vector. h)

Question

我正在解决 Sliding Window Maximum问题，但我在 Leetcode 上收到以下错误，但它在我的本地编译器 [VSCode] 上工作

Line 1034: Char 34: runtime error: addition of unsigned offset to 0x603000000040 overflowed to 0x603000000034 (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

代码如下:

#include <deque>

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& A, int k) {
        
        int _max = INT_MIN;
        vector<int> ans;
        for (int i = 0; i < k; ++i)
        {
            _max = max(_max, A[i]);
        }
        if (k == A.size()){
            return {_max};
        }
        
        ans.push_back(_max);
        deque<int> dq;
        dq.push_back(_max);

        for (int i = k; i < A.size(); ++i)
        {
            if (dq.empty())
            {
                dq.push_back(i);
                _max = A[i];
            }
            else
            {
                while (!dq.empty() && A[dq.front()] < A[i])
                {
                    dq.pop_front();
                }
                if (dq.empty())
                {
                    _max = A[i];
                }
                else
                {
                    _max = max(_max, A[i]);
                }
                dq.push_front(A[i]);
                ans.push_back(_max);
            }
        }

        return ans;
    }
};

Answer 1

看起来问题出在这里:A[dq.front()] < A[i];

正如我在运行时所见dq.front()取值 -3这不好，因为它是负指数。实际崩溃在这里 A[dq.front()] .所以您的代码中存在编程错误。

另外看起来您在此处推送了错误的索引:dq.push_front(A[i]) ，这意味着输入确实有负值，这是您没有想到的。

你可能想写 dq.push_front(i)而不是 dq.push_front(A[i]) .

固定程序看起来像这样:

#include <deque>

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& A, int k) {
        
        int _max = INT_MIN;
        vector<int> ans;
        for (int i = 0; i < k; ++i)
        {
            _max = max(_max, A[i]);
        }
        if (k == A.size()){
            return {_max};
        }
        
        ans.push_back(_max);
        deque<int> dq;
        dq.push_back(_max);

        for (int i = k; i < A.size(); ++i)
        {
            if (dq.empty())
            {
                dq.push_back(i);
                _max = A[i];
            }
            else
            {
                while (!dq.empty() && A[dq.front()] < A[i])
                {
                    dq.pop_front();
                }
                if (dq.empty())
                {
                    _max = A[i];
                }
                else
                {
                    _max = max(_max, A[i]);
                }
                dq.push_front(i);
                ans.push_back(_max);
            }
        }

        return ans;
    }
};