Path With Maximum Minimum Value

Description

null

Solution(javascript)

// /** NOTE
//  * 这题是所有路径的最优解
//  * 对比 329
//  * Dijkstra
//  * @param {number[][]} A
//  * @return {number}
//  */
// const maximumMinimumPath = function (A) {
//   const visited = A.map(xs => xs.map(() => false))
//   const dp = A.map(xs => xs.map(() => -Infinity))
//   const dfs = (row, colum, path = '') => {
//     if (row < 0 || row > A.length - 1
//       || colum < 0 || colum > A[row].length - 1
//     ) {
//       return -Infinity
//     }
//     if (visited[row][colum]) {
//       return dp[row][colum]
//     }
//     visited[row][colum] = true
//     if (row === A.length - 1 && colum === A[row].length - 1) {
//       console.log(path + A[row][colum])
//       dp[row][colum] = A[row][colum]
//       return A[row][colum]
//     }
//     const val = A[row][colum]
//     const right = dfs(row, colum + 1, path + val)
//     const left = dfs(row, colum - 1, path + val)
//     const up = dfs(row - 1, colum, path + val)
//     const down = dfs(row + 1, colum, path + val)


//     const current = Math.min(
//       Math.max(
//         left, right, up, down,
//       ),
//       val,
//     )
//     dp[row][colum] = current
//     return current
//   }
//   dfs(0, 0)
//   console.log(dp)
//   return dp[0][0]
// }


// /** 1: BruteForce
//  * @param {number[][]} A
//  * @return {number}
//  */
// const maximumMinimumPath = function (A) {
//   let max = -Infinity
//   const dfs = (row, colum, visited = {}, min) => {
//     const key = `${row}-${colum}`
//     if (row < 0 || row > A.length - 1
//       || colum < 0 || colum > A[row].length - 1
//       || visited[key]
//       || min <= max
//     ) {
//       return
//     }
//     visited[key] = true
//     const val = A[row][colum]
//     min = Math.min(min, val)
//     if (row === A.length - 1 && colum === A[row].length - 1) {
//       max = Math.max(
//         min,
//         max,
//       )
//       return
//     }
//     dfs(row, colum + 1, { ...visited }, min)
//     dfs(row, colum - 1, { ...visited }, min)
//     dfs(row - 1, colum, { ...visited }, min)
//     dfs(row + 1, colum, { ...visited }, min)
//   }
//   dfs(0, 0, {}, A[0][0])
//   return max
// }


/** 2: Union Find
 * @param {number[][]} A
 * @return {number}
 */
const maximumMinimumPath = function (A) {
  const values = A.reduce((acc, items) => acc.concat(items), [])
    .map((v, index) => [v, index])
    .sort((a, b) => a[0] - b[0])
  const parent = values.map((v, index) => index)
  const size = values.map(() => 1)

  const root = (a) => {
    while (a !== parent[a]) {
      parent[a] = parent[parent[a]]
      a = parent[a]
    }
    return a
  }
  const union = (a, b) => {
    const rootA = root(a)
    const rootB = root(b)
    if (rootA === rootB) {
      return
    }
    if (size[rootA] < size[rootB]) {
      parent[rootA] = rootB
      size[rootB] += size[rootA]
    } else {
      parent[rootB] = rootA
      size[rootA] += rootB
    }
  }
  const connected = (a, b) => root(a) === root(b)
  const visited = {}
  let min = Infinity
  const connectedHelp = (key1, row, colum) => {
    if (row < 0 || row > A.length - 1 || colum < 0 || colum > A[0].length - 1) {
      return
    }
    const key2 = row * A[0].length + colum
    if (visited[key2] === true) {
      union(key1, key2)
    }
  }
  for (let i = values.length - 1; i >= 0; i--) {
    const [value, key] = values[i]
    min = Math.min(min, value)
    visited[key] = true
    const row = Math.floor(key / A[0].length)
    const column = key % A[0].length
    connectedHelp(key, row + 1, column)
    connectedHelp(key, row - 1, column)
    connectedHelp(key, row, column + 1)
    connectedHelp(key, row, column - 1)


    if (connected(0, values.length - 1)) {
      return min
    }
  }
  return min
}