为何触发AddressSanitizer:DEADLYSIGNAL？栈溢出问题求助

问题描述 #

我编写了用于求解矩阵最长递增路径的C++代码，但运行时触发了AddressSanitizer栈溢出错误，代码与报错信息如下：

原代码 #

class Solution {
int maxRow, maxCol;
int x[4] = {1, -1, 0, 0};
int y[4] = {0, 0, 1, -1};

bool isValid(int row, int col){
    return (row >= 0 && row < maxRow && col >= 0 && col < maxCol);
}

int longestPath(int row, int col, vector<vector<int>>& matrix, vector<vector<int>>& dp){
    if(dp[row][col] != -1){
        return dp[row][col];
    }
    int longestCurrPath = 1; 
    for(int dir = 0; dir < 4; ++dir){
        int newRow = row + x[dir];
        int newCol = col + y[dir];
        if(isValid(newRow, newCol) && matrix[col][row] > matrix[newRow][newCol]){
            longestCurrPath = max(longestCurrPath, longestPath(newRow, newCol, matrix, dp) + 1);
        }
    }
    return dp[row][col] = longestCurrPath;
}

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        maxRow = matrix.size();
        maxCol = matrix[0].size();
        int LIP = 1;
        vector<vector<int>> dp(maxRow + 1, vector<int>(maxCol + 1, -1));
        for(int row = 0; row < maxRow; ++row){
            for(int col = 0; col < maxCol; ++col){
                if(dp[row][col] == -1)
                    LIP = max(LIP, longestPath(row, col, matrix, dp));
            }
        }
        return LIP;
    }
};

报错信息 #

AddressSanitizer:DEADLYSIGNAL
31ERROR: AddressSanitizer: stack-overflow on address 0x7ffe60cafff8 (pc 0x0000003466d2 bp 0x7ffe60cb0070 sp 0x7ffe60cb0000 T0)
31ABORTING

错误原因 #

1. 矩阵元素索引访问错误：在判断路径递增的条件中，错误地将行列索引写反（matrix[col][row]），正确的当前元素访问应该是matrix[row][col]。这个错误会导致两种问题：
   • 当矩阵的行数和列数不相等时，直接触发数组越界访问，引发未定义行为；
   • 逻辑判断完全颠倒，导致递归无法正确终止，陷入无限递归，最终耗尽栈空间触发栈溢出。
2. DP数组空间冗余：初始化DP数组时使用了maxRow + 1和maxCol + 1的尺寸，但实际只需要覆盖矩阵的有效行列范围（0到maxRow-1、0到maxCol-1），冗余空间虽不直接导致栈溢出，但可能引发后续的访问错误。

解决方法 #

修正关键错误点 #

• 修正矩阵元素的访问索引，将matrix[col][row]改为matrix[row][col]，同时调整判断逻辑为寻找比当前元素大的相邻元素（符合递增路径的要求）；
• 调整DP数组的初始化尺寸，去掉多余的+1，匹配矩阵的实际行列数；
• 增加空矩阵边界判断，避免输入为空时访问matrix[0].size()引发错误。

修正后的代码 #

class Solution {
int maxRow, maxCol;
int x[4] = {1, -1, 0, 0};
int y[4] = {0, 0, 1, -1};

bool isValid(int row, int col){
    return (row >= 0 && row < maxRow && col >= 0 && col < maxCol);
}

int longestPath(int row, int col, vector<vector<int>>& matrix, vector<vector<int>>& dp){
    if(dp[row][col] != -1){
        return dp[row][col];
    }
    int longestCurrPath = 1; 
    for(int dir = 0; dir < 4; ++dir){
        int newRow = row + x[dir];
        int newCol = col + y[dir];
        // 修正索引并调整为递增判断：相邻元素大于当前元素时才继续递归
        if(isValid(newRow, newCol) && matrix[newRow][newCol] > matrix[row][col]){
            longestCurrPath = max(longestCurrPath, longestPath(newRow, newCol, matrix, dp) + 1);
        }
    }
    return dp[row][col] = longestCurrPath;
}

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return 0; // 增加空矩阵判断
        maxRow = matrix.size();
        maxCol = matrix[0].size();
        int LIP = 1;
        // 修正DP数组尺寸
        vector<vector<int>> dp(maxRow, vector<int>(maxCol, -1));
        for(int row = 0; row < maxRow; ++row){
            for(int col = 0; col < maxCol; ++col){
                if(dp[row][col] == -1)
                    LIP = max(LIP, longestPath(row, col, matrix, dp));
            }
        }
        return LIP;
    }
};

内容的提问来源于stack exchange，提问作者yash mohan