JavaScript实现 - LeetCode刷题 -【太平洋大西洋水流问题】- 第 417 题 ！！！

题目：

LeetCode题目链接

题目截图：

解题步骤：

1.新建两个矩阵，分别记录能流到两个大洋的坐标
2.从海岸线，多管齐下，同时深度优先遍历图，过程中填充上述矩阵
3.遍历上面两个矩阵，找出同时能流到两个大洋的坐标

代码：

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function (matrix) {
  if (!matrix || !matrix[0]) return []; 
  const m = matrix.length; 
  const n = matrix[0].length; 
  const flow1 = Array.from({ length: m }, () => new Array(n).fill(false));
  const flow2 = Array.from({ length: m }, () => new Array(n).fill(false));  
  const dfs = (r, c, flow) => {
    flow[r][c] = true;  
    [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]].forEach(
      ([nr, nc]) => {
        if (
          nr >= 0 && nr < m &&
          nc >= 0 && nc < n &&
          !flow[nr][nc] &&
          matrix[nr][nc] >= matrix[r][c]
        ) {
          dfs(nr, nc, flow);
        }
      }
    );
  };
  for (let r = 0; r < m; r++) {
    dfs(r, 0, flow1); 
    dfs(r, n - 1, flow2); 
  }
  for (let c = 0; c < n; c++) { 
    dfs(0, c, flow1);
    dfs(m - 1, c, flow2);
  }
  const res = [];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (flow1[r][c] && flow2[r][c]) res.push([r, c]);
    }
  }
  return res;
};

时间复杂度分析：

时间复杂度是O(m * n)，因为每个点都过了一遍，m和n分别是矩阵的行数和列数

空间复杂度分析：

空间复杂度是O(m * n)

怎么样，是不是很简单，你学会了吗 ？

如果这篇文章能够帮助到您，希望您不要吝惜点赞????????和收藏????????，您的支持是我继续努力的动力 ???????? ！！！

本文地址：https://blog.csdn.net/weixin_44586544/article/details/112596060