C++ 栈溢出解决方法：最小努力路径问题

这段代码可能会出现栈溢出，原因可能是创建图的时候，id的计算有误，导致图中的节点数量过多，超出了栈的容量。

问题分析：

在创建图的时候，代码中使用 id = i * row + j 的方式来计算节点的索引。这个计算方式会导致，当 row 和 col 比较大时，id 的值也会非常大，从而导致图中节点的数量过多。如果图的节点数量超过了栈的容量，就会出现栈溢出。

解决方法：

检查id计算是否正确: 仔细检查代码中id的计算方式，确保其能够正确地反映图中的节点数量。2. 使用动态内存分配: 由于图中节点数量可能很大，建议使用动态内存分配来创建图，而不是使用栈上的内存空间。例如，可以使用 std::vector 或 new 来分配内存。

优化建议：

使用更小的数据类型: 如果 id 和 dis 不需要很大的值，可以尝试使用更小的数据类型，例如 short 或 char，以减少内存占用。2. 压缩图数据: 如果图中存在很多重复的边，可以考虑使用压缩图数据结构来减少内存占用。例如，可以使用邻接矩阵或邻接表来存储图，而不是使用 std::vector<std::vector<Node>>。

示例代码（使用动态内存分配）：

struct Node {
    int id;
    int dis;
    Node(int id, int dis) : id(id), dis(dis) {};
    friend bool operator < (Node n1, Node n2) {
        return  n1.dis < n2.dis;
    }
};

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int row = heights.size();
        int col = heights[0].size();
        // 使用vector<Node*>来存储图，每个元素指向一个Node节点
        vector<vector<Node*>> graph = vector<vector<Node*>>(row * col + 1, vector<Node*>(0));
        vector<int> minCost = vector<int>(row * col + 1, INT_MAX);
        //除开最后一行 最后一列
        for (int i = 0; i < row - 1; ++i) {
            for (int j = 0; j < col - 1; ++j) {
                int id = i * row + j;
                int des1 = i * row + j + 1;
                int cost1 = abs(heights[i][j + 1] - heights[i][j]);
                int des2 = (i + 1) * row + j;
                int cost2 = abs(heights[i + 1][j] - heights[i][j]);
                graph[id].push_back(new Node(des1, cost1));
                graph[id].push_back(new Node(des2, cost2));
            }
        }
        //最后一列
        for (int j = 0; j < row - 1; j++) {
            int id = j * row + col;
            int des = id + row;
            int cost = abs(heights[j + 1][col - 1] - heights[j][col - 1]);
            graph[id].push_back(new Node(des, cost));
        }
        //最后一行
        for (int i = 0; i < col - 1; i++) {
            int id = row * col + i;
            int des = id + 1;
            int cost = abs(heights[row - 1][i] - heights[row - 1][i + 1]);
            graph[id].push_back(new Node(des, cost));
        }
        int target = row * col - 1;
        priority_queue<Node> q;
        q.push(Node(0, 0));
        while (!q.empty()) {
            Node nd = q.top();
            q.pop();
            if (nd.id == target) {
                return nd.dis;
            }
            if (nd.dis > minCost[nd.id]) {
                continue;
            }
            for (auto& neighbour : graph[nd.id]) {
                int weight = neighbour->dis + nd.dis;
                if (weight < minCost[neighbour->id]) {
                    minCost[neighbour->id] = weight;
                    q.push(Node(neighbour->id, weight));
                }
            }
        }
        return INT_MAX;
    }
};

注意：

使用动态内存分配时，需要在使用完后手动释放内存，以避免内存泄漏。可以通过在程序结束时调用 delete 或 delete[] 来释放内存。

希望这些建议能够帮助你解决代码中的栈溢出问题，并优化代码的性能。