# 1102. Path With Maximum Minimum Value
###### tags: `Leetcode` `Medium` `BFS` `Greedy` `Priority Queue`
Link: https://leetcode.com/problems/path-with-maximum-minimum-value/
## 思路 $O(MN * log(MN))$
不是Dijkstra, dijkstra和这道题的区别在于dijkstra需要维护一个array，里面存现在每个点对应的值，而这道题由于每个点的值都只会更新一次，只要一个值被更新了，它就不会再被改变了，所以不需要维护那样的array，只需要用bfs+greedy做，dijkstra之所以需要维护，是因为对于一个点B来说，B可能通过A的值+A到B的weight更新一次，但不代表它从别的路径绕一个圈子再走到B算出来的值会比原来的值大

这题的思路是**用maxHeap，每次找最大值，然后在过程中记录最小值**

和[0778. Swim in Rising Water](https://hackmd.io/0P3Zi0RZQ1Stxj3pDvXciQ)做比较，非常类似
可以和[1514. Path with Maximum Probability](https://hackmd.io/B7M8f6PUSdqHzZry7hDpSA)以及1631. Path With Minimum Effort作比较
## Code

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        pq = []
        m, n = len(grid), len(grid[0])
        heappush(pq, [-grid[0][0], 0, 0])
        dirs = [[0,1], [1,0], [-1,0], [0,-1]]
        visited = [[False for i in range(n)] for j in range(m)]
        ans = grid[0][0]
        visited[0][0] = True
        while pq:
            val, x, y = heappop(pq)
            ans = min(-val, ans)
            if x==m-1 and y==n-1: return ans
            for dir in dirs:
                nextX = dir[0]+x
                nextY = dir[1]+y
                if nextX>=0 and nextX<m and nextY>=0 and nextY<n and not visited[nextX][nextY]:
                    visited[nextX][nextY] = True
                    heappush(pq, [-grid[nextX][nextY], nextX, nextY])
        return ans

class Solution {
    public int maximumMinimumPath(int[][] grid) {
        Queue<int[]> q = new PriorityQueue<>((a,b)->(grid[b[0]][b[1]]-grid[a[0]][a[1]]));
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        q.add(new int[]{0,0});
        int ans = grid[0][0];
        
        while(!q.isEmpty()){
            int[] curr = q.poll();
            ans = Math.min(ans, grid[curr[0]][curr[1]]);
            if(curr[0]==m-1 && curr[1]==n-1) return ans;
            for(int[] dir:dirs){
                int nextx = curr[0]+dir[0];
                int nexty = curr[1]+dir[1];
                if(nextx>=0 && nextx<m && nexty>=0 && nexty<n && !visited[nextx][nexty]){
                    int[] next = new int[]{nextx, nexty};
                    visited[nextx][nexty] = true;
                    q.add(next);
                }
            }
        }
        return ans;
    }
}