对撞双指针专题：接雨水(盛最多水)系列问题

Leetcode11. 盛最多水的容器、Leetcode42. 接雨水  两个问题都涉及到水的容积和收集，但由于它们所处理的问题空间、背景和解决方法的不同，它们有着显著的区别。

• "盛最多水的容器"关注于找到两个柱子形成的最优组合来盛最多的水，计算的是特定两线段间的面积——只需考虑两条线（两个高度）和它们之间的距离。

• "接雨水"关注于计算整个地形能积累的雨水总量，计算的所有可能积水区域面积的总和——需要考虑每个凹槽的高度和宽度，并累加所有凹槽的容量

虽然都可以使用双指针法，但在"接雨水"中，边界点主要作为遍历的起点和终点，雨水的积累更多发生在内部较低的位置。

所以"接雨水"在计算每一步的累积量时考虑了更多局部最优到全局最优的转换逻辑。

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i,height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

示例 1： 输入：[1,8,6,2,5,4,8,3,7]    输出：49 

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

容纳的水量是由 左右两端直线中较低直线的高度 * 两端直线之间的距离 所决定的。所以我们应该使得 较低直线的高度尽可能的高，这样才能使盛水面积尽可能的大。

对撞双指针

设两指针 i， j ，指向的水槽板高度分别为 h[i]h[i] ，此状态下水槽面积为 S(i, j)。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ：

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1 变短：

• 若向内 移动短板 ：水槽的短板 min(h[i], h[j]) 可能变大，因此下个水槽的面积 可能增大 。
  

• 若向内 移动长板 ：水槽的短板 min(h[i], h[j])不变或变小，因此下个水槽的面积 一定变小 。

因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

最终稿代码

function maxArea(height) {
  if (!height?.length) return 0;
  let left = 0, right = height.length - 1;
  let area = 0;
  while (left < right) {
    if (height[left] < height[right]) { //容水量只与短板有关
      res = Math.max(area, height[left] * (right - left));
      left++; //向内移动短板有可能让结果变大
    } else {
      res = Math.max(area, height[right] * (right - left));
      right--;
    }
  }
}

接雨水

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

示例1：输入：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 个单位的雨水（蓝色部分表示雨水）。

这个之前在《单调栈系列：下一个更大元素、每日温度、接雨水  》已经求解了，如果使用双指针，效率更高

我们开两个数组 r_max 和 l_max 充当备忘录， l_max[i] 表⽰位置 i 左边最⾼的柱⼦⾼度，r_max[i] 表⽰位置 i 右边最⾼的柱⼦⾼度。预先把这两个数组计算好，避免重复计算。

然后遍历数组，计算当前位置的雨水量：Math.min(左边最高的柱子， 右边最高的柱子) - 当前柱子的高度

遍历解法

class Solution {
    //带备忘录的暴力解法
 
    public int trap(int[] height) {
        int n = height.length;
        if(n <= 1){
            return 0;
        }
 
        //定义两个数组，分别存储height[0,,,i]和height[i,,,n - 1]的最大值
        int[] leftMaxNum = new int[n];
        int[] rightMaxNum = new int[n];
        //初始化
        leftMaxNum[0] = height[0];
        rightMaxNum[n - 1] = height[n - 1];
        //计算i左侧的最大值
        for(int i = 1; i < n; i++){
            leftMaxNum[i] = Math.max(leftMaxNum[i - 1], height[i]);
        }
        for(int j = n - 2; j >= 0; j--){
            rightMaxNum[j] = Math.max(rightMaxNum[j + 1], height[j]);
        }
 
        //遍历计算每个位置能接住的雨水量
        int res = 0;
        for(int k = 1; k < n - 1; k++){
            res += Math.min(leftMaxNum[k], rightMaxNum[k]) - height[k];
        }
 
        return res;
    }
}

双指针解法

class Solution {
    //3.双指针技巧，边走边算，降低时间复杂度和空间复杂度
 
    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        //左右指针
        int left = 0;
        int 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;
    }
}

接雨水 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。

相比42.接雨水，貌似只是将 一维数组变成了二维数 ，但如果直接照抄的 双指针解法（《对撞双指针专题：接雨水(盛水)系列问题 》），把一维方法照搬到二维来，对每个位置（i，j）找左右的最高点a、b和上下的最高点c、d，然后取abcd中最小值就是（i，j）处能接到的最多雨水

这种方法的错误在于没有考虑二维上的连通性（在二维空间中，不仅需要考虑左右，还需要考虑上下，而且不能仅仅考虑最大高度，还需要考虑包围性，这就导致问题的复杂性一下上升了一个维度），因此本题不适合 双指针等常规解法。

木桶效应

我们可以将问题进行拆解，考虑一个最简单的规模，即周围四个格子（上下左右）的高度是确定的，那么该格所能接的水取决于周围四个格子最短的那一个。简单说就是木桶效应，最短的格子决定了能装多少水。那能不能把问题简化成四个格子呢？

首先我们考虑一个较大的范围，从宏观角度上，将整个二维空间视作一个木桶，那么能装多少水取决于最外层的格子高度

根据木桶原理，接到的雨水的高度由这个容器周围最短的木板来确定的。我们可以知道容器内水的高度取决于最外层高度最低的方块，如图 1 所示：

我们假设已经知道最外层的方块接水后的高度的最小值，则此时我们根据木桶原理，肯定可以确定最小高度方块的相邻方块的接水高度。我们同时更新最外层的方块标记，我们在新的最外层的方块再次找到接水后的高度的最小值，同时确定与其相邻的方块的接水高度

class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap.length <= 2 || heightMap[0].length <= 2) {
            return 0;
        }
        int m = heightMap.length;
        int n = heightMap[0].length;
        boolean[][] visit = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    pq.offer(new int[]{i * n + j, heightMap[i][j]});
                    visit[i][j] = true;
                }
            }
        }
        int res = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            for (int k = 0; k < 4; ++k) {
                int nx = curr[0] / n + dirs[k];
                int ny = curr[0] % n + dirs[k + 1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
                    if (curr[1] > heightMap[nx][ny]) {
                        res += curr[1] - heightMap[nx][ny];
                    }
                    pq.offer(new int[]{nx * n + ny, Math.max(heightMap[nx][ny], curr[1])});
                    visit[nx][ny] = true;
                }
            }
        }
        return res;
    }
}

可视化教材：https://www.bilibili.com/video/BV18P411n7AF/

参考文章：

Leetcode接雨水系列问题 https://blog.csdn.net/qq_39144436/article/details/124315096

转载本站文章《对撞双指针专题：接雨水(盛最多水)系列问题》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9096.html