Connected to rainwater series problems

author ：Grey

Original address ： Connected to rainwater series problems

LeetCode 42. Rainwater collection

Main idea ： Consider each location , How much water can be left on the top , Add up , Is the total receiving water .

among , The rightmost and leftmost tops do not receive water , Because the water will flow away from both sides .

Based on the above logic , At least we can judge , If the length of the array is less than or equal to 2, Go straight back to 0 Share water .

When the length of the array is greater than 2, We need to consider , from 1 No. 1 to The length of the array -2, How much water can be connected to the top of each position .

Set four variables

        int l = 1;
        int r = arr.length - 2;
        //  What is the bottleneck of the current height on the left side 
        int lMax = arr[0];
        //  What is the bottleneck of the current height on the right 
        int rMax = arr[arr.length - 1];

lMax and rMax As the bottleneck of the left and right sides in the current state , Where we actually traverse from l To r, look down arr[l] and arr[r] The location is based on the amount of water that can be collected by the bottlenecks on the left and right sides .

First , Although there are two bottleneck values , however , When we settle accounts , It can only be settled with a small bottleneck value , Because if you settle with a large bottleneck value , A small bottleneck will lower the current settlement value （ Barrel effect ）.

therefore , There are two situations ：

Situation 1 ：lMax > rMax

Situation two ：lMax <= rMax

In this case , for example

under these circumstances , We can be sure arr[r] How much water can be connected to the position , because arr[r] And the bottleneck on the right is a definite relationship , Although the bottleneck on the left is smaller than arr[r] Big , It's the water that makes the right bottleneck arr[r] The collected water flows away , So at this time

arr[r] The amount of water that can be collected on the is arr[r] and rMax Difference between , If it's a negative number , Then for 0, Equivalent to not receiving water , here ,r Position traversal completed , The bottleneck on the right is updated to Math.max(arr[r],rMax), Follow the example above , Now the bottleneck on the right becomes arr[r] Value on . Here's the picture

In this state , The relatively small bottleneck is rMax, You can also settle the current arr[r] The amount of water at the location , still 0. Then continue to update the right bottleneck , Here's the picture

here , The bottleneck on the left is the smaller one , Update now arr[l] The amount of water overhead , namely ：arr[l] and lMax The difference between and 0 The bigger one , And then move l The pointer , Update the bottleneck on the left （ because arr[l] No value lMax Big , So the bottleneck on the left side remains the same lMax Location ）, Here's the picture .

Next lMax < rMax, Continue settlement arr[l], Move l And update lMax

The following process is the same , The schematic diagram is as follows

until l>r

All water is collected .

For the full code, see

    public static int trap(int[] arr) {
    
        if (arr == null || arr.length <= 2) {
    
            return 0;
        }
        int result = 0;
        int l = 1;
        int r = arr.length - 2;
        int lMax = arr[0];
        int rMax = arr[arr.length - 1];
        while (l <= r) {
    
            if (lMax < rMax) {
    
                //  Settlement left 
                result += Math.max(0, lMax - arr[l]);
                lMax = Math.max(lMax, arr[l++]);
            } else {
    
                //  Settlement right side 
                result += Math.max(0, rMax - arr[r]);
                rMax = Math.max(rMax, arr[r--]);
            }
        }
        return result;
    }

Time complexity O(N), Spatial complexity O(1).

LeetCode 407. Rainwater collection II

Main idea

It's the same as one-dimensional thinking , The problem of two-dimensional rainwater connection is also to locate the bottleneck first , The bottleneck of one-dimensional rainwater connection is located from the left and right ends , The two-dimensional bottleneck is to locate around the matrix . To find the smallest bottleneck around , We need to use one Heap （ Organize by value ）, Add the values of four weeks to the small root heap , The pop-up value is the minimum bottleneck . First , We need to wrap the original matrix , To design a Node data structure , It is used to store a certain value and its position information in the original matrix .

    public static class Node {
    
        public int v; //  value 
        public int i; //  Row position 
        public int j; //  Column position 

        public Node(int v, int i, int j) {
    
            this.i = i;
            this.j = j;
            this.v = v;
        }
    }

What is stored in the small root pile is Node, according to Node Of v To organize ,

PriorityQueue<Node> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.v));

Every time a Node When , Move this position up, down, left and right （ Make sure you don't cross the line ） To settle , After settlement , Add the settled position to the small root heap （ There is no need to add the positions that have already been added ）, Because you need to know which locations have been added to the small root heap , So set a two-dimensional boolean Array , Used to mark whether a certain position has been entered .

boolean[][] isEntered = new boolean[m][n];

if (isEntered[i][j]) {
    
    //  A certain location has entered the small root pile 
} else {
    
    //  Otherwise, I have not entered 
}

First , We add the points around the matrix to the small root pile , And the isEntered Set it up

        //  Here are two for loop , Is to put all around into a pile of small roots 
        for (int i = 0; i < m; i++) {
    
            heap.offer(new Node(heightMap[i][0], i, 0));
            heap.offer(new Node(heightMap[i][n - 1], i, n - 1));
            isEntered[i][0] = true;
            isEntered[i][n - 1] = true;
        }
        for (int i = 0; i < n; i++) {
    
            heap.offer(new Node(heightMap[0][i], 0, i));
            heap.offer(new Node(heightMap[m - 1][i], m - 1, i));
            isEntered[0][i] = true;
            isEntered[m - 1][i] = true;
        }

Then we set up a max, It is used to identify which is the smallest bottleneck at this time . The next process is ：

One element pops up from the small root heap at a time , See if you can update the bottleneck value , Let's see if its position in all directions crosses the boundary , If you don't cross the border , Direct settlement of values in all directions , Add up to water In this variable , At the same time, all directions Node Add the small root pile , cycle , Until the small root heap is empty .water The value of is the amount of water collected .

For the full code, see

    public static int trapRainWater(int[][] heightMap) {
    
        if (null == heightMap || heightMap.length <= 2 || heightMap[0].length <= 2) {
    
            return 0;
        }
        int m = heightMap.length;
        int n = heightMap[0].length;
        int max = 0;
        PriorityQueue<Node> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.v));
        boolean[][] isEntered = new boolean[m][n];
        //  Here are two for loop , Is to put all around into a pile of small roots 
        for (int i = 0; i < m; i++) {
    
            heap.offer(new Node(heightMap[i][0], i, 0));
            heap.offer(new Node(heightMap[i][n - 1], i, n - 1));
            isEntered[i][0] = true;
            isEntered[i][n - 1] = true;
        }
        for (int i = 0; i < n; i++) {
    
            heap.offer(new Node(heightMap[0][i], 0, i));
            heap.offer(new Node(heightMap[m - 1][i], m - 1, i));
            isEntered[0][i] = true;
            isEntered[m - 1][i] = true;
        }
        int water = 0;
        while (!heap.isEmpty()) {
    
            //  The weakest position 
            Node weakest = heap.poll();
            max = Math.max(weakest.v, max);
            int i = weakest.i;
            int j = weakest.j;
            if (i + 1 < m && !isEntered[i + 1][j]) {
    
                water += Math.max(0, max - heightMap[i + 1][j]);
                isEntered[i + 1][j] = true;
                heap.offer(new Node(heightMap[i + 1][j], i + 1, j));
            }
            if (i - 1 >= 0 && !isEntered[i - 1][j]) {
    
                water += Math.max(0, max - heightMap[i - 1][j]);
                isEntered[i - 1][j] = true;
                heap.offer(new Node(heightMap[i - 1][j], i - 1, j));
            }
            if (j + 1 < n && !isEntered[i][j + 1]) {
    
                water += Math.max(0, max - heightMap[i][j + 1]);
                isEntered[i][j + 1] = true;
                heap.offer(new Node(heightMap[i][j + 1], i, j + 1));
            }
            if (j - 1 >= 0 && !isEntered[i][j - 1]) {
    
                water += Math.max(0, max - heightMap[i][j - 1]);
                isEntered[i][j - 1] = true;
                heap.offer(new Node(heightMap[i][j - 1], i, j - 1));
            }
        }
        return water;
    }

    public static class Node {
    
        public int v;
        public int i;
        public int j;

        public Node(int v, int i, int j) {
    
            this.i = i;
            this.j = j;
            this.v = v;
        }
    }

Spatial complexity O(M*N), The time complexity is O(M*N*log(M+N)).

more

Algorithm and data structure notes