【经典算法题】接雨水

【经典算法题】接雨水 【经典算法题】接雨水 Leetcode 0042 接雨水

题目描述：Leetcode 0042 接雨水

分析

• 本题的考点：数组。

• 核心思路：我们求出每个位置能存储的水量，最后加到一起就可以得到答案，如下图五个地方的水量相加即可：

• 那么如何求解每个位置可以存放的雨水？我们可以预先处理处两个数组left_max和right_max。left_max[i]表示height[0]~height[i]中最高的柱子，right_max[i]表示height[i]~height[n-1]中最高的柱子。

• 则对于位置i，可以存储的雨水为：min(left_max[i], right_max[i]) - height[i]。

• 这一题其实是Leetcode 0407 接雨水 II一个简单版本，本题是二维版本，Leetcode 0407 接雨水 II是三维版本。

代码

• C++

class Solution {
public:
    int trap(vector &height) {

        int n = height.size();
        if (n == 0) return 0;

        vector left_max(n), right_max(n);

        left_max[0] = height[0];
        for (int i = 1; i < n; i++) left_max[i] = max(left_max[i - 1], height[i]);
        right_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) right_max[i] = max(right_max[i + 1], height[i]);

        int res = 0;
        for (int i = 0; i < n; i++) res += min(left_max[i], right_max[i]) - height[i];

        return res;
    }
};

• Java

class Solution {
    public int trap(int[] height) {

        int n = height.length;
        if (n == 0) return 0;

        int[] left_max = new int[n], right_max = new int[n];

        left_max[0] = height[0];
        for (int i = 1; i < n; i++) left_max[i] = Math.max(left_max[i - 1], height[i]);
        right_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) right_max[i] = Math.max(right_max[i + 1], height[i]);

        int res = 0;
        for (int i = 0; i < n; i++) res += Math.min(left_max[i], right_max[i]) - height[i];

        return res;
    }
}

• Python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0

        left_max = [0 for _ in range(n)]
        right_max = [0 for _ in range(n)]

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        res = 0
        for i in range(n):
            res += min(left_max[i], right_max[i]) - height[i]
        return res

时空复杂度分析

• 时间复杂度： O ( n ) O(n) O(n)。n为数组长度。

• 空间复杂度： O ( n ) O(n) O(n)。n为数组长度。

Leetcode 0407 接雨水 II

题目描述：Leetcode 0407 接雨水 II

分析

• 本题的考点：dijkstra。

• 关于单元最短路径的问题可以参考网址。

• 和Leetcode 0042 接雨水的做法类似，我们需要找到从当前位置到达大海的所有路径中的最大值的最小值（从该点到大海有多条路径，每条路径都有一个最大值，我们需要在这些最大值中找到最小的那一个），这个最小值就是下雨后该点的高度。

• 类似于最短路问题，最短路问题是求解路径总和的最小值；这里的问题是求出所有路径中最大值的最小值。这一题可以采用最短路径的方式求解，下面使用dijkstea的思想求解该问题。

• 本题的起点可以设为大海，相当于新建了一个虚拟源点s。从s向四周的每个格子都连接一条边权为0的边，所有起点不能到达的点标记为正无穷，然后从s求单源最短路径即可（从a走到b的边权定义为b所在位置的高度）。

• 代码实现时不需要真实地将s建立出来，直接将s到达的所有点加入优先队列即可。

• 设 d i s t [ i ] [ j ] dist[i][j] dist[i][j]表示从s到 ( i , j ) (i, j) (i,j)所有路径中边权最大值的最小值，如果从 ( i , j ) (i, j) (i,j)能到达 ( x , y ) (x, y) (x,y)，则根据定义一定有： d i s t [ x ] [ y ] ≤ m a x ( d i s t [ i ] [ j ] , h [ x ] [ y ] ) dist[x][y] le max(dist[i][j], h[x][y]) dist[x][y]≤max(dist[i][j],h[x][y])。解释如下：

• 下面还有一个问题，就是要证明一下可以使用dijkstea算法求解该问题。本题可以证明入队的元素（假设是 ( x , y ) (x, y) (x,y)）就是最小值，不可能被其他点更新了。

• 首先四周元素入队时是合法的，因为是所有从当前点到大海的路径的最大值的最小值，因为每条路径都包含该点，因此最小值大于等于该点，又因为有一条路径可以取到该点，因此四周的值就是对应的权重。

• 当图中的点b被第一次扩展到时，假设由相邻的a点扩展到，b周围的另外三个点要么在队列中，要么还没入队，因此b点对应的最终dist值更大。这里想要说明被扩展到的点的dist值是递增的。

代码

• C++

class Solution {
public:
    static const int N = 210;

    bool st[N][N];  // 判重数组, 为true代表该点已经求出答案

    struct Node {
        int x, y, d;  // d: 到达(x, y)的所有路径中边权最大值的最小值, 上述分析中的dist
        bool operator<(const Node &t) const {
            return d > t.d;  // 默认大顶堆，需要使用小顶堆
        }
    };

    int trapRainWater(vector> &h) {

        int n = h.size(), m = h[0].size();
        
        int res = 0;
        priority_queue heap;

        // 将四周的点加入优先队列
        for (int i = 0; i < n; i++) {
            heap.push({i, 0, h[i][0]});
            heap.push({i, m - 1, h[i][m - 1]});
            st[i][0] = st[i][m - 1] = true;
        }
        for (int i = 1; i < m - 1; i++) {
            heap.push({0, i, h[0][i]});
            heap.push({n - 1, i, h[n - 1][i]});
            st[0][i] = st[n - 1][i] = true;
        }

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        while (heap.size()) {

            Node t = heap.top();
            heap.pop();

            for (int i = 0; i < 4; i++) {
                int x = t.x + dx[i], y = t.y + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && !st[x][y]) {
                    st[x][y] = true;
                    if (h[x][y] < t.d) res += t.d - h[x][y];
                    heap.push({x, y, max(t.d, h[x][y])});
                }
            }
        }

        return res;
    }
};

• Java

class Solution {
    static final int N = 210;  // 但是提交时存在(200,200)的矩阵
    boolean[][] st = new boolean[N][N];  // 判重数组, 为true代表该点已经求出答案

    static class Node implements Comparable {
        int x, y, d;  // d: 到达(x, y)的所有路径中边权最大值的最小值

        public Node(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }

        @Override
        public int compareTo(Node o) {
            return d - o.d;  // 默认小顶堆，需要使用小顶堆
        }
    }

    public int trapRainWater(int[][] h) {

        int n = h.length, m = h[0].length;

        int res = 0;
        PriorityQueue heap = new PriorityQueue<>();

        // 将四周的点加入优先队列
        for (int i = 0; i < n; i++) {
            heap.add(new Node(i, 0, h[i][0]));
            heap.add(new Node(i, m - 1, h[i][m - 1]));
            st[i][0] = st[i][m - 1] = true;
        }
        for (int i = 1; i < m - 1; i++) {
            heap.add(new Node(0, i, h[0][i]));
            heap.add(new Node(n - 1, i, h[n - 1][i]));
            st[0][i] = st[n - 1][i] = true;
        }

        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

        while (!heap.isEmpty()) {

            Node t = heap.remove();

            for (int i = 0; i < 4; i++) {
                int x = t.x + dx[i], y = t.y + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || st[x][y]) continue;
                st[x][y] = true;
                if (h[x][y] < t.d) res += t.d - h[x][y];
                heap.add(new Node(x, y, Math.max(h[x][y], t.d)));
            }
        }
        return res;
    }
}

时空复杂度分析

• 时间复杂度： O ( n × l o g ( n ) ) O(n times log(n)) O(n×log(n))。n为数组边长，不妨设n是两个边中较大的那一个。

• 空间复杂度： O ( n 2 ) O(n^2) O(n2)。n为数组长度。