“This is the third day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

Topic describes

This is 407 on LeetCode. Receiving rain WATER II. Difficulty means difficult.

Tag: “Graph shortest”, “priority queue (heap)”

Given a matrix of MXNM x NMXN, where the values are non-negative integers representing the heights of each cell in a two-dimensional height diagram, please calculate the maximum volume of rain water that can be connected to the shapes in the diagram.

Example 1:

Input: heightMap = [,4,3,1,3,2 [1], [3,2,1,3,2,4], [2,3,3,2,3,1]] output: 4: after the rain, the rain will be above the blue square. The total amount of rain water is 1+2+1=4.Copy the code

Example 2:

Input: heightMap = [,3,3,3,3 [3], [3,2,2,2,3], [3,2,1,2,3], [3,2,2,2,3], [3,3,3,3,3]] output: 10Copy the code

Tip:

  • m == heightMap.length
  • n == heightMap[i].length
  • 1 <= m, n <= 200

  • 0 < = h e i g h t M a p [ i ] [ j ] < = 2 ∗ 1 0 4 0 <= heightMap[i][j] <= 2 * 10^4

Dijkstra transform + Priority queue (heap)

First of all, the outermost circle (the boundary) does not receive any rain.

We define the maximum height that appears in the path from point (x,y)(x, y)(x,y) to the boundary as “path height”. The path height HHH must satisfy h>=heightMap[x][y] H >=heightMap[x][y] H >=heightMap[x][y].

The essence of the problem is to find “from the point
( x . y ) (x, y) What is the minimum of all path heights to the boundary “, the minimum of this path height and
( x . y ) (x, y) Height of itself
h e i g h t M a p [ x ] [ y ] heightMap[x][y] The difference is the amount of rain that can be received at that point.

PS. If you don’t understand this, you can try to consider it from a realistic perspective: If the location is an outlet (to a steady stream of water and spread in all directions), the position of how much water bearing, eventually depends on the height of all paths through the minimum value (the water will eventually be the path to the height of the intercepting minimum), namely the water outlet end formed as “minimum path height” and “outlet starting height difference between”.

Let’s think about how to compute the minimum of all the path heights at (x,y)(x, y).

If it is to find the minimum sum of all paths starting from (x,y)(x, y)(x,y), it can directly use Dijkstra and other single-source shortest circuit algorithm to solve.

In this question, we need to find the minimum height of all paths. We need to transform Dijkstra.

Firstly, “the path from (x,y)(x, y)(x,y) to the boundary” can also be regarded as “the path from the boundary to the point (x,y)(x, y)(x,y)”. After conversion operation, the path from the boundary to the point (x,y)(x, y)(x,y) is a multi-source point problem.

We can consider the introduction of “super source point” for simplification: the super source point is connected to all boundary cells with an edge of weight 000, thus further transforming the problem into “finding the minimum height of the path from the super source point to (x,y)(x, y)(x,y)”.

Similar to Dijkstra in finding the shortest circuit, we can equate “relaxation operation of updating neighboring points with out-queuing element” to “updating the rain amount of adjacent grids with out-queuing element”.

If we can guarantee that the height updated by the platoon element is the final height (or that the height of the platoon element is the final height), then the correctness of this practice is guaranteed by Dijkstra’s correctness.

As we know, for the boundary grid, since it cannot receive any rain (i.e. the final height is the starting height), they can join the queue first.

Then consider how to team out and update the neighborhood to ensure correctness.

For a position (x,y)(x, y)(x,y), according to the “barrel principle”, its final height depends on the minimum final height of the adjacent points in the four directions.

This leads us to do this using priority queues (heaps) : Create a small root heap to store (x,y,h)(x, y,h)(x, y, H) triplet information (HHH is the final height of position (x,y)(x, y)(x,y)), each time to update the neighboring point with the outqueue element, because it is a small root heap, can ensure that the outqueue element is the smallest height of the element to be updated. The updated element is updated to its final height, and then the updated element is enqueued, repeating the process until all positions are updated.

For implementation, we don’t need to actually create the super source, just start by putting all the boundary points into the priority queue. We also need to use the VisvisVIS array to avoid repeated updates since only the height updated by the first queuing element is the final height of each point.

Code:

class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]);
        boolean[][] vis = new boolean[m][n];
        for (int i = 0; i < n; i++) {
            q.add(new int[] {0, i, heightMap[0][i]});
            q.add(new int[]{m - 1, i, heightMap[m - 1][i]});
            vis[0][i] = vis[m - 1][i] = true;
        }
        for (int i = 1; i < m - 1; i++) {
            q.add(new int[]{i, 0, heightMap[i][0]});
            q.add(new int[]{i, n - 1, heightMap[i][n - 1]});
            vis[i][0] = vis[i][n - 1] = true;
        }
        int[][] dirs = new int[] [] {{1.0}, {-1.0}, {0.1}, {0, -1}};
        int ans = 0;
        while(! q.isEmpty()) {int[] poll = q.poll();
            int x = poll[0], y = poll[1], h = poll[2];
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (vis[nx][ny]) continue;
                if (h > heightMap[nx][ny]) ans += h - heightMap[nx][ny];
                q.add(new int[]{nx, ny, Math.max(heightMap[nx][ny], h)});
                vis[nx][ny] = true; }}returnans; }}Copy the code
  • Time complexity: all point in and out of a priority queue (heap), complexity of O (log (m ∗ n) ⁡ n) (m ∗) O (n) (m * \ log {} (m * n)) O (m ∗ n) log (n) (m ∗)
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

The last

This is No.407 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.