大家好！我是曾续缘😇

今天是《LeetCode 热题 100》系列

发车第 7 天

双指针第 4 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

给定 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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

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

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

难度：💝💝💝

解题方法

下雨后能装多少水 是不是就等于 每一列能装多少水的总和。

对于当前这一列能装多少水, 是由它左边最高的柱子和右边最高柱子共同决定的， 更具体点是有两者中最小的柱子决定的,当然还需要减去当前这一列的柱高。

我们使用l,r（双指针）来表示左右两边遍历到的柱子，从最左和最右开始，ml,mr表示左右两边目前遍历到的最高的柱子高度，（不是最高的不影响答案）。ml由l向右遍历计算得到，mr由r向左遍历计算得到。

对于l这一列来说, 能装多少水,是由它左边最高的柱子和右边最高柱子共同决定的，也可以是由两者最小的柱子决定的，而不需要知道两者具体的值是多少。

其中ml就是已知的l左边最高的柱子， mr只代表了目前r位置右边最高的柱子, 不代表l位置右边的最高的柱子高度, 因此还不能求能装多少水。

但是如果知道了ml < mr，再根据mr的定义可以推理出l右边最高柱子肯定是大于等于当前的mr，也就是间接知道了左边最高的柱子低于右边最高柱子，也就是知道了两者中最小的柱子(左柱子)，因此可以求出当前l这个位置装的水。

对于r的位置分析,同理.

Code

查看代码

class Solution {
    public int trap(int[] height) {
        int n = height.length, l = 0, r = n - 1, ml = 0, mr = 0;
        int ans = 0;
        while(l < r){
            ml = Math.max(ml, height[l]);
            mr = Math.max(mr, height[r]);
            if(ml < mr){
                ans += ml - height[l];
                l++;
            }else{
                ans += mr - height[r];
                r--;
            }
        }
        return ans;
    }
}