1631.md

1631. Path With Minimum Effort

Leetcode link

解题思路——并查集

本题给了我们一个二维数组，并要求我们找到从左上角到右下角元素波动最小（就是靠近的两个元素差值的最大值最小）的路径。

我们可以把这个问题简化成：找到一个图上的一条路径，这条路径最长的部分必须是所有路径最长的部分的最小值。

因此，我们可以使用基于并查集的 Kruskal 算法来做，具体思路如下：

1. 计算所有相邻元素之间的距离（就是两个元素之间的差值）
2. 将所有的距离从小到大排序
3. 从最小的距离开始，依次将元素加入并查集中
4. 检查左上角的起点与右下角的终点是否已经在同一个组中，如果是则返回当前的距离
5. 如果不是则回到第三步继续计算

C++

class UnionFind {
 private:
  vector<int> root;
  vector<int> rank;

 public:
  UnionFind(int size) : root(size), rank(size) {
    for (int i = 0; i < size; i++) {
      root[i] = i;
      rank[i] = 1;
    }
  }

  int find(int x) {
    if (x == root[x]) {
      return x;
    }
    return root[x] = find(root[x]);
  }

  void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
      if (rank[rootX] >= rank[rootY]) {
        root[rootY] = rootX;
        rank[rootX] += rank[rootY];
      } else {
        root[rootX] = rootY;
        rank[rootY] += rank[rootX];
      }
    }
  }
};

class Solution {
 public:
  int minimumEffortPath(vector<vector<int>> &heights) {
    int col = heights[0].size(), row = heights.size();
    vector<tuple<int, int, int>> edges;
    //  计算节点与下面、右边的边距（effort）
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        int position = i * col + j;
        if (j < col - 1) {
          edges.push_back(
              {position, position + 1, abs(heights[i][j] - heights[i][j + 1])});
        }
        if (i < row - 1) {
          edges.push_back({position, position + col,
                           abs(heights[i][j] - heights[i + 1][j])});
        }
      }
    }

    sort(edges.begin(), edges.end(),
         [](auto &a, auto &b) { return get<2>(a) < get<2>(b); });

    UnionFind uf(col * row);
    int start = 0, end = col * row - 1;
    for (auto [cell1, cell2, distance] : edges) {
      uf.unionSet(cell1, cell2);
      if (uf.find(start) == uf.find(end)) {
        return distance;
      }
    }

    return 0;
  }
};

Javascript

class UnionFind {
 constructor(size) {
     this.root = new Array(size);
     this.rank = new Array(size);
    for (let i = 0; i < size; i++) {
      this.root[i] = i;
      this.rank[i] = 1;
    }
  }

  find(x) {
    if (x == this.root[x]) {
      return x;
    }
    return this.root[x] = this.find(this.root[x]);
  }

  unionSet(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX != rootY) {
      if (this.rank[rootX] >= this.rank[rootY]) {
        this.root[rootY] = rootX;
        this.rank[rootX] += this.rank[rootY];
      } else {
        this.root[rootX] = rootY;
        this.rank[rootY] += this.rank[rootX];
      }
    }
  }
};

var minimumEffortPath = function(heights) {
    const row = heights.length,
          col = heights[0].length;
    let edges = [];
//     计算元素与下面，右边的边距
    for(let i=0;i<row;i++) {
        for(let j=0;j<col;j++) {
            let position = i * col + j;
            if(i<row - 1) {
                edges.push([position, position + col, Math.abs(heights[i][j] - heights[i+1][j])]);
            }
            if(j < col -1) {
                edges.push([position, position+1, Math.abs(heights[i][j] - heights[i][j+1])]);
            }
        }
    }
//     对边距排序（小 -> 大）
    edges.sort((a, b)=> a[2] - b[2]);
    
    const uf = new UnionFind(col * row);
    const start = 0,
          end = col * row - 1;
    
    for(let edge of edges) {
        const [cell1, cell2, effort] = edge;
        uf.unionSet(cell1, cell2);
        if(uf.find(start) === uf.find(end)) {
            return effort;
        }
    }
    
    return 0;
};

解题思路——Dijkstra

我们可以把题目化简成求图上指定起点与终点的最短路径。只是最短路径的定义不再是路径累加，而是用最长的一段路径代表。

于是，我们就可以用 Dijkstra 的思想来做了，具体思路如下：

1. 我们需要一个数组 dist 来记录任意点到起点的最短路径，并在一开始初始化数组元素为∞
2. 我们还需要一个优先队列 pq 来记录当前 “发现” 的元素以及当前的最短路长度
3. 最后我们维护一个已到达数组 visited 来保存已经确定了最短路的元素
4. 然后就可以开始 Dijkstra 了，区别在于更新 dist 的条件是当前节点到起始点最长的一段路径要小于 dist 里面记录的长度

C++

class Solution {
 private:
  int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  bool inRange(int x, int y, int row, int col) {
    return x >= 0 && x < row && y >= 0 && y < col;
  }

 public:
  int minimumEffortPath(vector<vector<int>>& heights) {
    int row = heights.size(), col = heights[0].size();

    auto Cmp = [](const auto& e1, const auto& e2) {
      auto&& [x1, y1, d1] = e1;
      auto&& [x2, y2, d2] = e2;
      return d1 > d2;
    };

    // {row, col, distance}
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                   decltype(Cmp)>
        pq(Cmp);
    pq.push({0, 0, 0});

    vector<int> dist(row * col, INT_MAX);
    dist[0] = 0;
    vector<bool> visited(row * col);

    while (!pq.empty()) {
      auto [x, y, distance] = pq.top();
      pq.pop();
      int position = x * col + y;
      if (visited[position]) {
        continue;
      }
      if (x == row - 1 && y == col - 1) {
        break;
      }
      visited[position] = true;
      for (int i = 0; i < 4; i++) {
        int nextX = x + direction[i][0];
        int nextY = y + direction[i][1];
        if (inRange(nextX, nextY, row, col) &&
            max(distance, abs(heights[nextX][nextY] - heights[x][y])) <
                dist[nextX * col + nextY]) {
          dist[nextX * col + nextY] =
              max(distance, abs(heights[nextX][nextY] - heights[x][y]));
          pq.push({nextX, nextY, dist[nextX * col + nextY]});
        }
      }
    }

    return dist[col * row - 1];
  }
};