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

Question

我正在解决滑动窗口最大值问题，但我在 Leetcode 上收到以下错误，但它在我的本地编译器 [VSCode] 上运行

第1034行：Char 34：运行时错误：将无符号偏移量添加到0x603000000040溢出到0x603000000034（stl_vector.h）
摘要：UndefinedBehaviorSanitizer：未定义行为 /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;
    }
};

Answer 2

我遇到了同样的错误，我确保没有负值被推入队列。 代码： 类解决方案{ 民众： int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1};

bool safe(vector<vector<int>>& grid, int x, int y){
    return (x >= 0 && x < grid.size(), y >= 0 && y < grid[0].size());
}

void dfs(vector<vector<int>>& grid, int x, int y, 
queue<pair<int, int>> &q){
    grid[x][y] = 2;
    for(int z = 0; z < 4; z++){
        int r = x + dx[z];
        int c = y + dy[z];
        if(safe(grid, r, c)){
            if(grid[r][c] == 1) {
                q.push({r, c});
                dfs(grid, r, c, q);
            }
        }
    }
}

int bfs(vector<vector<int>>& grid, 
queue<pair<int, int>> &q){
    int dist = 0, min_dist = INT_MAX;
    
    while(!q.empty()){
        int s = q.size();
        while(s-- > 0){
            pair<int, int> temp;
            temp = q.front();
            q.pop();
            for(int z = 0; z < 4; z++){
                int r = temp.first + dx[z];
                int c = temp.second + dy[z];

                if(safe(grid, r, c)){
                    if(grid[r][c] == 1) min_dist = min(min_dist, dist);
                    grid[r][c] = 2;
                    q.push({r, c});
                }
            }
        }
        dist++;
    }
    return min_dist;
}

int shortestBridge(vector<vector<int>>& grid) {
    //int n = grid.size();
    bool flag = false;
    //vector<vector<bool>> vis(n, vector<bool>(n, false));
    queue<pair<int, int>> q;
    for(int i = 0; i < grid.size(); i++){
        for(int j = 0; j < grid[0].size(); j++){
            if(grid[i][j] == 1){
                q.push({i, j});
                dfs(grid, i, j, q);
                flag = true;
                break;
            }
        }
        if(flag == true) break;
    }
    return bfs(grid, q);
}

};

问题链接：https://leetcode.com/problems/shortest-bridge/