接雨水题型

①题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

题解

/**
 * @see https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class Solution {

    // 暴力版
//    public int trap(int[] height) {
//        int n = height.length;
//        int ans = 0;
//        for (int i = 1; i < n - 1; i++) {
//            int l_max = 0, r_max = 0;
//            // 找到左边最高的柱子
//            for (int j = i; j >= 0; j--) {
//                l_max = Math.max(l_max, height[j]);
//            }
//            // 找到右边最高的柱子
//            for (int j = i; j < n; j++) {
//                r_max = Math.max(r_max, height[j]);
//            }
//            ans += Math.min(l_max, r_max) - height[i];
//        }
//        return ans;
//    }

    // 备忘录优化暴力
//    public int trap(int[] height) {
//        int n = height.length;
//        if (n == 0) {
//            return 0;
//        }
//        int ans = 0;
//        int[] l_max = new int[n];
//        int[] r_max = new int[n];
//        // 初始化
//        l_max[0] = height[0];
//        r_max[n - 1] = height[n - 1];
//        // 从左至右 l_max
//        for (int i = 1; i < n; i++) {
//            l_max[i] = Math.max(height[i], l_max[i - 1]);
//        }
//        // 从右至左 r_max
//        for (int i = n - 2; i >= 0; i--) {
//            r_max[i] = Math.max(height[i], r_max[i + 1]);
//        }
//        for (int i = 1; i < n - 1; i++) {
//            ans += Math.min(l_max[i], r_max[i]) - height[i];
//        }
//        return ans;
//    }

    // 双指针法
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        int ans = 0, left = 0, right = n - 1;

        int l_max = height[0];
        int r_max = height[n - 1];

        while (left <= right) {
            l_max = Math.max(l_max, height[left]);
            r_max = Math.max(r_max, height[right]);

            if (l_max < r_max) {
                ans += l_max - height[left];
                left++;
            } else {
                ans += r_max - height[right];
                right--;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
    }

}

②题目

给你一个 m x n 的矩阵,其中的值均为正整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。
示例:

给出如下 3x6 的高度图:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

返回 4 。

如上图所示,这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。

 

 

下雨后,雨水将会被存储在这些方块中。总的接雨水量是4。

题解

import java.util.PriorityQueue;

/**
 * @see https://leetcode-cn.com/problems/trapping-rain-water-ii/
 */
public class Solution {

    public int trapRainWater(int[][] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int n = heights.length;
        int m = heights[0].length;

        // 记录是否被访问
        boolean[][] visited = new boolean[n][m];
        // 优先队列 小根堆
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>((o1, o2) -> o1[2] - o2[2]);

        // 最外层
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    priorityQueue.add(new int[]{i, j, heights[i][j]});
                    visited[i][j] = true;
                }
            }
        }

        int res = 0;
        int[] dir = {-1, 0, 1, 0, -1};
        while (!priorityQueue.isEmpty()) {
            int[] poll = priorityQueue.poll();
            // 四个方向
            for (int i = 0; i < 4; i++) {
                int nx = poll[0] + dir[i];
                int ny = poll[1] + dir[i + 1];
                // 位置合法且未访问
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                    // 外围最小 > 当前高度, 则可灌水
                    if (poll[2] > heights[nx][ny]) {
                        res += poll[2] - heights[nx][ny];
                    }
                    priorityQueue.offer(new int[]{nx, ny, Math.max(heights[nx][ny], poll[2])});
                    visited[nx][ny] = true;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
    }

}

粤ICP备17005116号