本文主要是介绍Path With Maximum Minimum Value，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].
The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.
A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).
Example 1:
Input: [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation:
The path with the maximum score is highlighted in yellow.
Example 2:
Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2思路：破题思路，想最后一个点，上边和左边过来，每条路径的value是这条路径上的最小，但是我首先是跟上边和左边过来的最大值进行比较，所以pq是为了处理每次四个方向扩散，首先扩散最大的value，这题跟waterII很类似，water是每次过来取四周最小值，先进行扩散，这里相反，每次取最大值进行扩散，T: O(mn*lg(mn)); 注意，dijkstra的算法，visited一定要在外面，而不是if block里面进行判断，否则会漏掉最优解；
class Solution {public class Node {public int x;public int y;public int value;public Node(int x, int y, int value) {this.x = x;this.y = y;this.value = value;}}public int maximumMinimumPath(int[][] grid) {int m = grid.length;int n = grid[0].length;PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> (b.value - a.value));pq.offer(new Node(0, 0, grid[0][0]));int[][] dirs = {{0,1},{0,-1},{-1,0},{1,0}};boolean[][] visited = new boolean[m][n];while(!pq.isEmpty()) {Node node = pq.poll();if(node.x == m - 1 && node.y == n - 1) {return node.value;}if(visited[node.x][node.y]) {continue;}visited[node.x][node.y] = true;for(int[] dir: dirs) {int nx = node.x + dir[0];int ny = node.y + dir[1];if(0 <= nx && nx < m && 0 <= ny && ny < n && !visited[nx][ny]) {pq.offer(new Node(nx, ny, Math.min(grid[nx][ny], node.value)));}}}return -1;}
}这篇关于Path With Maximum Minimum Value的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
