mzoe666888

V1

2022/04/09阅读:16主题:兰青

内卷大厂系列《接雨水问题二连击》

大厂高频算法面试题:《接雨水问题系列》,您将学到接水问题的实质是什么,通过不同的方法求解,一步一步推出最优解,希望在时间复杂度和空间复杂度上有所帮助、有所认知。

一、接雨水 I

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

示例 1:

接雨水 I
接雨水 I
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

接雨水 I

1、分析

一维接水问题,潜台词:边缘是不可能留下水的,想想是不是,边缘上方的水会流到左边或右边,所以最左边的柱子或最右边的柱子上是留不下水的,所以不用考虑盛水问题。

i位置的格子往左边遇到的高度和往右边遇到的高度求最小值就是遇到的盛水瓶颈

i位置的格子能盛的雨水量 = max(min(左max,右max) - arr[i],0),arr[i]为当前柱子的高度

方法一:遍历数组,当前来到i位置,从0~i-1求出左边最大高度,从i+1~N-1求出右边最大高度,时间复杂度为O(N²)

方法二:提前求出左边最大值和右边最大值,生成2个预处理数组用来加速求解左边最大值和右边最大值过程,每次来到i位置,从预处理数组中获取即可,时间复杂度为O(N),额外空间复杂度为O(N)

方法三:只需要一个右边预处理数组,左边最大值更新用一个变量记录即可,时间复杂度为O(N),额外空间复杂度为O(N)

方法四利用双指针技巧,有限变量实现最优解,左指针L开始指向数组1位置,右指针R开始指向数组N-2位置,如果左边最大值小于等于右边最大值,说明当前盛水瓶颈在左边,不需要看后边的高度(i+1~N-1),因为右边最小高度都大于左边高度,如果左边最大值大于右边最大值,说明当前盛水瓶颈在右边,不需要看之前的高度(0~i-1),左指针和右指针不回退,时间复杂度为O(N),额外空间复杂度为O(1)

2、实现

2.1、方法一

public static int water(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int N = arr.length;
    int water = 0;
    for (int i = 1; i < N - 1; i++) {
        int leftMax = Integer.MIN_VALUE;
        for (int j = 0; j < i; j++) { // 左边求一个最大值
            leftMax = Math.max(leftMax, arr[j]);
        }
        int rightMax = Integer.MIN_VALUE;
        for (int j = i + 1; j < N; j++) { // 右边求一个最大值
            rightMax = Math.max(rightMax, arr[j]);
        }
        water += Math.max(Math.min(leftMax, rightMax) - arr[i], 0);
    }
    return water;
}

2.2、方法二

public static int water(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int N = arr.length;
    int[] leftMaxs = new int[N]; // 左边最大值预处理数组
    leftMaxs[0] = arr[0];
    for (int i = 1; i < N; i++) {
        leftMaxs[i] = Math.max(leftMaxs[i - 1], arr[i]);
    }
    int[] rightMaxs = new int[N];
    rightMaxs[N - 1] = arr[N - 1]; // 右边最大值预处理数组
    for (int i = N - 2; i >= 0; i--) {
        rightMaxs[i] = Math.max(rightMaxs[i + 1], arr[i]);
    }
    int water = 0;
    for (int i = 1; i < N - 1; i++) {
        water += Math.max(Math.min(leftMaxs[i - 1], rightMaxs[i + 1]) - arr[i], 0);
    }
    return water;
}

2.3、方法三

public static int water(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int N = arr.length;
    int[] rightMaxs = new int[N];
    rightMaxs[N - 1] = arr[N - 1]; // 右边最大值预处理数组
    for (int i = N - 2; i >= 0; i--) {
        rightMaxs[i] = Math.max(rightMaxs[i + 1], arr[i]);
    }
    int water = 0;
    int leftMax = arr[0]; // 左边最大值
    for (int i = 1; i < N - 1; i++) {
        water += Math.max(Math.min(leftMax, rightMaxs[i + 1]) - arr[i], 0);
        leftMax = Math.max(leftMax, arr[i]); // 更新左边最大值
    }
    return water;
}

2.4、方法四

public static int water(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int N = arr.length;
    int L = 1// 0位置不可能盛下水
    int leftMax = arr[0]; 
    int R = N - 2// N-1位置不可能盛下水
    int rightMax = arr[N - 1];
    int water = 0;
    while (L <= R) {
        if (leftMax <= rightMax) { // 说明瓶颈在左边
            water += Math.max(0, leftMax - arr[L]);
            leftMax = Math.max(leftMax, arr[L++]);
        } else { // 说明瓶颈在右边
            water += Math.max(0, rightMax - arr[R]);
            rightMax = Math.max(rightMax, arr[R--]);
        }
    }
    return water;
}

二、接雨水 II

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

示例 1:

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后,雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:

输入: 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]]
输出: 10

接雨水 II

1、分析

二维接水问题,边缘位置还是不可能盛下水的,二维接水问题可以看成 “锅盖”,锅盖外圈好比锅边,内圈好比锅面,如下所示内部的1上方都能留下2格水。

准备一个小根堆,数据封装成一个节点Node,Node中有3个属性,分别代表高度、所在的行,所在的列,小根堆的比较策略:高度从小到大排序。

第一步:先把外层一圈的节点加入小根堆。

第二步:依次弹出堆顶节点,从上下左右4个方向判断每个节点的高度是否大于当前节点的高度,需要增加排重机制,防止重复节点入小根堆结算重复雨水。

  • 上边节点是否加入过小根堆,没有的话,获取上边节点的高度与当前节点的高度比较
  • 下边节点是否加入过小根堆,没有的话,获取下边节点的高度与当前节点的高度比较
  • 左边节点是否加入过小根堆,没有的话,获取左边节点的高度与当前节点的高度比较
  • 右边节点是否加入过小根堆,没有的话,获取右边节点的高度与当前节点的高度比较

细节判断看代码实现

2、实现

public static class Node {
    public int value;
    public int row;
    public int col;

    public Node(int v, int r, int c) {
        value = v;
        row = r;
        col = c;
    }

}

// 比较器
public static class NodeComparator implements Comparator<Node{

    @Override
    public int compare(Node o1, Node o2) {
        return o1.value - o2.value;
    }

}

public static int trapRainWater(int[][] heightMap) {
    if (heightMap == null || heightMap.length == 0 || heightMap[0] == null || heightMap[0].length == 0) {
        return 0;
    }
    int N = heightMap.length;
    int M = heightMap[0].length;
    // isEnter[i][j] == true  之前进过
    //  isEnter[i][j] == false 之前没进过
    boolean[][] isEnter = new boolean[N][M];
    // 小根堆
    PriorityQueue<Node> heap = new PriorityQueue<>(new NodeComparator());
    // 将外层一圈添加进小根堆,注意边界不要重复添加
    for (int col = 0; col < M - 1; col++) { // 最上边一行添加进小根堆
        isEnter[0][col] = true;
        heap.add(new Node(heightMap[0][col], 0, col));
    }
    for (int row = 0; row < N - 1; row++) { // 最右边一列添加进小根堆
        isEnter[row][M - 1] = true;
        heap.add(new Node(heightMap[row][M - 1], row, M - 1));
    }
    for (int col = M - 1; col > 0; col--) { // 最下边一行添加进小根堆
        isEnter[N - 1][col] = true;
        heap.add(new Node(heightMap[N - 1][col], N - 1, col));
    }
    for (int row = N - 1; row > 0; row--) { // 最左边一列添加进小根堆
        isEnter[row][0] = true;
        heap.add(new Node(heightMap[row][0], row, 0));
    }
    int water = 0// 每个位置的水量,累加到water上去
    int max = 0// 每个node在弹出的时候,如果value更大,更新max,否则max的值维持不变
    while (!heap.isEmpty()) {
        Node cur = heap.poll();
        max = Math.max(max, cur.value);
        int r = cur.row;
        int c = cur.col;
        if (r > 0 && !isEnter[r - 1][c]) { // 如果有上面的位置并且上面位置没进过堆
            water += Math.max(0, max - heightMap[r - 1][c]);
            isEnter[r - 1][c] = true;
            heap.add(new Node(heightMap[r - 1][c], r - 1, c));
        }
        if (r < N - 1 && !isEnter[r + 1][c]) { // 如果有下面的位置并且下面位置没进过堆
            water += Math.max(0, max - heightMap[r + 1][c]);
            isEnter[r + 1][c] = true;
            heap.add(new Node(heightMap[r + 1][c], r + 1, c));
        }
        if (c > 0 && !isEnter[r][c - 1]) { // 如果有左面的位置并且左面位置没进过堆
            water += Math.max(0, max - heightMap[r][c - 1]);
            isEnter[r][c - 1] = true;
            heap.add(new Node(heightMap[r][c - 1], r, c - 1));
        }
        if (c < M - 1 && !isEnter[r][c + 1]) { // 如果有右面的位置并且右面位置没进过堆
            water += Math.max(0, max - heightMap[r][c + 1]);
            isEnter[r][c + 1] = true;
            heap.add(new Node(heightMap[r][c + 1], r, c + 1));
        }
    }
    return water;
}

三、总结

接水问题

  • 在一维数组中确定左右两侧哪个是短板
  • 在二维数组中利用堆来确定短板,实质max变大就是换湖了,一片湖一片湖的算水

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1